[BOJ] 11724번: 연결 요소의 개수 | BFS/DFS | Python
문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
풀이
처음에 연결 요소라는 말을 몰라서, 검색해봤더니 결국 한 줄로 다음을 의미하는 것 같다.
연결 요소(Connected Component): 그래프에서 하나의 간선으로라도 연결되어 있는 정점들의 그룹.
즉, 그래프의 노드가 10개 있는데, 10개가 모두 연결되어 있지는 않을 수도 있을 것이다. 10개 중 7개는 연결되어 있고, 나머지 3개도 연결되어 있으나, 이 7개와 3개의 두 그룹 사이에는 어떠한 간선도 없을 경우에 연결 요소는 2개가 되는 것이다.
어떤 정점을 시작으로 연결된 노드들을 따라 방문하다가 연결된 모든 노드들을 방문하였지만, 그래프의 모든 노드들을 방문한 것이 아닌 경우에는, 방문하지 않은 노드에서 다시 탐색을 진행하면 되는 것이다. 이렇게 탐색을 진행한 횟수를 카운팅하면 해당 그래프의 연결 요소 개수를 구할 수 있게 된다. 탐색 방법은 DFS/BFS 모두 가능하다. 메모리와 시간은 두 방법 간 큰 차이는 없었다.
Solution1: BFS
import sys
from collections import deque
# BFS: 너비우선탐색
def bfs(graph, v, visit):
que = deque([v])
visit[v] = True
while que:
v = que.popleft()
for i in graph[v]:
if not visit[i]:
que.append(i)
visit[i] = True
read = sys.stdin.readline
N, M = map(int, read().split())
graph = [ [] for _ in range(N+1) ]
for _ in range(M):
v1,v2 = map(int, read().split())
graph[v1].append(v2)
graph[v2].append(v1)
visit = [False] * (N+1)
cnt = 0
for v in range(1, N+1):
if visit[v]: continue
bfs(graph, v, visit)
cnt += 1
print(cnt)
Solution2: DFS
한편, DFS에서는 처음에 재귀 제한 에러(Recursion Error)가 떠서 찾아보니 파이썬에서는 재귀 제한 횟수가 1000~3000으로 설정되어 있기 때문에 이 제한을 해제해야 했다. sys.setrecursionlimit(10000)으로 하여, 재귀 제한 횟수를 늘렸더니, 문제 없이 진행됐다.
import sys
sys.setrecursionlimit(10000) # 재귀 제한을 확대해야 함.
# DFS: 깊이우선탐색
def dfs(graph, v, visit):
visit[v] = True
for i in graph[v]:
if not visit[i]:
dfs(graph, v, visit)
read = sys.stdin.readline
N, M = map(int, read().split())
graph = [ [] for _ in range(N+1) ]
for _ in range(M):
v1,v2 = map(int, read().split())
graph[v1].append(v2)
graph[v2].append(v1)
visit = [False] * (N+1)
cnt = 0
for v in range(1, N+1):
if visit[v]: continue
dfs(graph, v, visit)
cnt += 1
print(cnt)
