[탐색/DFS] 백준 11724 연결 요소의 개수 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11724번: 연결 요소의 개수

 

 

 

2. 문제 풀이

 연결 요소의 개수를 구하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

 BFS, DFS 모두 사용가능합니다. 이번에는 DFS로 풀어보겠습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#dfs 탐색(탐색할 그래프, 시작 노드, 방문여부 리스트)
def dfs(graph, node, visited):
    visited[node] = True #시작 노드 방문
    # 인접 노드를 재귀적으로 방문
    for i in graph[node]:
        if not visited[i]: #방문하지 않은 노드라면
            dfs(graph, i, visited) #해당 노드를 시작 노드로 dfs

#그래프 입력
N, M = map(int, input().split())
graph = [ [i] for i in range(N+1) ]
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False]*(N+1) #방문 여부 리스트
cnt = 0 #연결 요소 개수
for i in range(1, N+1):
    if not visited[i]: #방문하지 않은 노드라면
        cnt += 1 #연결요소를 하나 늘리고
        dfs(graph, i, visited) #dfs탐색
print(cnt)

 DFS로 1번 노드부터 N번 노드까지 탐색합니다. 이미 탐색한 노드는 건너 뛰며, 탐색하지 않은 노드가 나오면 연결 요소 개수를 1개 늘립니다. (이전 dfs에서 방문하지 못한 노드는 '다른 연결요소'에 있는 노드입니다.)

 다만, 위의 코드로만 제출하면 파이썬 재귀 에러(Recursion Error)가 발생합니다. dfs는 재귀 방식을 사용하므로, 시스템이 정한 최대 재귀횟수를 늘려줘야 합니다.

 

 

sys.setrecursionlimit(10**6) #재귀 깊이를 늘리는 코드

 위 코드를 추가하면 정상적으로 동작합니다.