백준 11724번 / 연결 요소의 개수 (Python, 파이썬, 백준, 알고리즘)

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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(10000)

N, M = map(int, sys.stdin.readline().split())
graph = [[0]*(N + 1) for _ in range(N + 1)]
visited = [False] * (N + 1)
cnt = 0

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

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

 

python은 재귀제한이 걸려있기 때문에 재귀 허용치가 넘어가면 런타임에러가 발생한다.
(기본적으로 설정되있는 최대 재귀 깊이는 1,000이라 합니다.)
이러한 이유 때문에 sys.setrecursionlimit(10000) 상단에 작성하여 줍니다.

모든 요소가 연결되어 있다면, cnt의 값은 1로 출력 됩니다.
정의한 dfs() 실행 후에 방문처리 되지 않은 요소가 있다는 것은 별개의 연결 요소가 존재한다는 것이기 때문에 방문 처리 후, cnt를 증가 시켜줍니다.