[백준][Python 파이썬] 11724번 연결 요소의 개수

 

bfs 또는 dfs 방식으로 그래프를 탐색하면 된다. 

만약 모든 노드가 이어져 있다면, 즉 연결 요소의 개수가 1개라면 그래프 탐색으로 모든 노드를 방문할 수 있을 것이다. 

그게 아니라면 연결 요소의 개수만큼 그래프를 탐색해야 모든 노드를 방문할 수 있을 것이다. 

 

u, v 노드 사이의 간선을 저장하는 방법은 2차원 배열도 있고 여러 가지가 있으나, 여기서는 collections.defaultdict()을 사용해서 딕셔너리에 노드 값 하나와 노드와 이어진 다른 노드들의 리스트를 키-값으로 맵핑하였다. 

 

또한 여기서는 그래프의 모든 노드를 순회하면서, 방문하지 않은 노드가 있을 경우 그 노드를 시작점으로 bfs 탐색을 진행하였다. 

한 번 탐색할 때마다 연결 요소의 개수도 증가하므로 ans 변수의 값을 1씩 증가시켰다. 

 

import sys
from collections import defaultdict, deque

input = sys.stdin.readline
N, M = map(int, input().split())
graph = defaultdict(list)
visited = [False] * (N+1)

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
def bfs(start):
    Q = deque([start])
    visited[start] = True
    while Q:
        node = Q.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = True
                Q.append(n)

ans = 0
for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        ans += 1

print(ans)