[Baekjoon/Python] 11724번: 연결 요소의 개수(BFS)

# Baekjoon 11724번: 연결 요소의 개수
import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
visited = [None for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
cnt = 0

for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)


def BFS(i):
    global cnt
    q = deque()
    q.append(graph[i])
    visited[i] = True
    
    while q:
        for v in q.popleft():
            if visited[v] == None:
                visited[v] = True
                q.append(graph[v])
        
        
for i in range(1, N+1):
    if visited[i] == None:
        cnt +=1
        BFS(i)
        
print(cnt)

그래프를 이용한 BFS/DFS 알고리즘 문제이다. 문제에서 서로 연결된 정점들을 알려줬기 때문에 이를 이용하여 그래프를 먼저 만들도록 한다. 그리고 for문으로 정점을 차례대로 거치면서 방문하지 않았을 경우에는 cnt에 1을 더한 후 BFS 알고리즘을 진행한다.
BFS 내부에서는 deque를 이용해 정점의 그래프를 추가하고, 방문을 True로 변환해준다. 그 뒤 while문 안에서 deque에 있는 그래프를 추출한 뒤 그 안에 있는 정점 요소들을 방문하도록 한다.  

예제 2번의 graph를 그림으로 나타내면 위와 같다. 각 정점마다 연결되어 있는 정점이 요소로 속해져있는 것을 확인할 수 있다. 이것이 그래프 문제를 시작할때의 기본이다.