[Algorithm] [Python] 백준/BOJ - 11724 _ 연결 요소의 개수

11724 - 연결 요소의 개수

문제

---

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

---

첫째 줄에 연결 요소의 개수를 출력한다.

제출 코드

---

import sys
sys.setrecursionlimit(10000)


def dfs(node):
    visited[node] = True
    for i in adj[node]:
        if not visited[i]:
            dfs(i)


# n : 정점 개수 , m : 간선 개수
n, m = map(int, sys.stdin.readline().split())

# 최적화를 위한 인접 리스트 활용
adj = [ [] for _ in range(n+1)]
visited = [False] * (n+1)
cnt = 0

for _ in range(m):
    src,dest = map(int, sys.stdin.readline().split())
    adj[src].append(dest)
    adj[dest].append(src)

# 1번 부터 n번 까지의 노드 순회하며 방문여부 확인 -> 방문이 안되었다는건 연결 요소가 아니라는 것
for i in range(1, n+1):         
    if not visited[i]:
        cnt += 1
        dfs(i)
print(cnt)

 

문제 풀이

---

본 문제는 입력값으로 전달되는 그래프의 정보를 기반으로 이를 모델링하여 연결 요소의 개수를 구하는 문제다.

그래프의 정보를 입력받으면 이를 인접 리스트 기반으로 그래프를 구현한다.

이후 DFS 기반의 탐색을 통해 노드 방문시 visited 배열에 해당 인덱스 값을 체크하는 함수를 작성한다.

이후 루프를 통해 인접 리스트를 해당 원소의 visited 여부를 확인하고 아직 방문하지 않았을 경우 cnt값을 증가시켜 다시 dfs를 실행한다.