백준 11724 파이썬 - 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

문제

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

코드

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [[]for i in range(n + 1)]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [0] * (n + 1)
def bfs(v):
    q = deque()
    q.append(v)
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = 1
result = 0
for i in range(1, n + 1):
    if not visited[i]:
        bfs(i)
        result += 1
sys.stdout.write(str(result))

풀이

서로 연결되어 있는 노드들의 모임이 몇개 있는지 세는 문제이다. 이 문제에서 그것을 연결 요소라고 불렀다.

BFS를 활용해 탐색하면 된다. DFS를 사용하면 재귀 호출 횟수(1000회)가 파이썬에서는 제한되어 있다고 해서 오류가 뜰 수 있다.

물론 해결방법은 있다. DFS로 풀고 싶으면 import sys를 하고 sys.setecursionlimit() 괄호 안에 10000 정도 넣어주면 된다고 한다.