[백준] 11724 연결 요소의 개수 / python

문제

https://www.acmicpc.net/problem/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(10**6)
input = sys.stdin.readline

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

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

cnt = 0

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

for i in range(1, N+1):
    if not visited[i]:
        dfs(graph, i, visited)
        cnt += 1

print(cnt)

 

처음에는 최대로 연결되는 개수라고 이해를 했는데

이 문제에서 말하는 연결 요소는 연결되어 있는 그래프의 개수 나 영역의 개수였다.

DFS/BFS를 한 번 수행했을 때 방문되는 모든 노드를 묶어서 하나의 연결 요소라고 할 수 있다.

따라서 DFS/BFS가 수행되는 횟수가 연결 요소의 개수가 된다.

 

모든 노드를 순차적으로 방문하면서 아직 방문되지 않은 노드에 대해서

DFS/BFS를 실행하는 과정이 for문이다.

DFS/BFS가 한 번 끝날 때마다 cnt+1을 하게 되면 연결 요소의 개수를 구할 수 있다.

 

 

 

처음에 런타임 에러 (RecuresionError)가 떴다.

RecursionError는 재귀와 관련된 에러이다. 가장 많이 발생하는 이유는 파이썬이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때이다.

파이썬이 정한 최대 깊이는 sys.getrecursionlimit()을 통해 확인할 수 있다.

백준의 채점 서버에서 이 값은 1000으로 되어 있다.

파이썬이 정한 최대 재귀 깊이를 변경하여 에러를 해결하였다.

sys.setrecursionlimit(10**6)

이 함수를 사용하면 소스의 최대 재귀 깊이를 1,000,000 정도로 크게 설정할 수 있다.