[BOJ] 11724 연결 요소의 개수 - python

백준 11724번 연결 요소의 개수 문제이다.

 

import sys
sys.setrecursionlimit(10000)

N, M = map(int,sys.stdin.readline().split())

visited = [0]*(N+1)
graph = [[0]*(N+1) for _ in range(N+1)] 

def dfs(n):
    visited[n] = 1
    for i in range(1,N+1):
        if visited[i] == 0 and graph[n][i] == 1:
            dfs(i) 

for _ in range(M): 
    a, b = map(int, sys.stdin.readline().split()) 
    graph[a][b] = 1 
    graph[b][a] = 1 

count = 0
for _ in range(1,N+1):
    if visited[_] == 0:
        dfs(_)
        count += 1		# dfs 재귀에서 돌아온 경우 count 증가
        
print(count)

 

해당 문제에서는 재귀 횟수 제한을 증가시켜줘야한다.

그렇지 않으면 런타임 에러가 발생하는데, Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어지기 때문이다.

BOJ의 채점 서버에서 이 값은 1,000으로 되어있다.