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

❓문제

[실버2] 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) 같은 간선은 한 번만 주어진다.

출력
첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

---

💭 아이디어

문제를 보자마자 유기농 배추, 음료수 얼리기 문제와 비슷한 느낌임을 받았다.

이 문제는 DFS, BFS 모두로 풀이 가능하다.
유기농 배추, 음료수 얼리기의 경우 상하좌우로 이동하며 조건을 확인하는 반면, 이 문제는 그래프와 연결되어 있으면(인접해있으면) 이동하면 된다. BFS의 경우 while문이 끝날 때까지 반복하면 하나의 연결 요소에 대해서 모두 방문처리가 된다. DFS의 경우 재귀호출을 하고, 끝나면 하나의 연결 요소에 대해 모두 방문처리가 된다. 그 후, 방문하지 않은 노드에 대해 다시 BFS, DFS를 수행하면 된다.

그래프 탐색의 기본적인 풀이는 dfs, bfs 원리를 알면 풀 수 있다.
이 문제에서는 반복문을 돌며 방문여부에 따라 함수를 호출하고, 함수를 나오면 연결요소를 증가시키는 부분이 중요한 것 같다.

---

❗ 풀이

두 방식 모두에서 인접리스트로 그래프를 표현하였다.

1. DFS

import sys
sys.setrecursionlimit(10 ** 6) # 재귀함수의 깊이 늘리기

def dfs(v):
    visited[v] = 1
    
    for a in graph[v]:
        if visited[a] == 0: # 인접한 노드가 아직 방문되지 않았다면
            dfs(a)
    return True

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
# print(graph)

visited = [0] * (n+1)

answer = 0
for i in range(1, n+1):
    if visited[i] == 0:
        dfs(i)
        answer += 1
print(answer)

2. BFS

from collections import deque
import sys

def bfs(v):
    q = deque([v])
    
    visited[v] = 1
    while q:
        now = q.popleft()
        for a in graph[now]:
            if visited[a] == 0:
                q.append(a)
                visited[a] = 1

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0] * (n+1)

answer = 0
for i in range(1, n+1):
    if visited[i] == 0:
        bfs(i)
        answer += 1
print(answer)

---

✅ Comment

1. DFS로 구현하였을 때 recursion error가 발생하였다.
   이는 유기농배추 문제를 풀었을 때 겪었던 부분인지라 python3에서 재귀함수의 깊이가 1000으로 매우 얕아 생긴 오류임을 바로 알고, sys 모듈을 import 하고 setrecursionlimit() 함수를 통해 재귀함수의 깊이를 늘려주었다.

2. DFS, BFS 모두에서 시간초과가 발생하였다.
   무슨 이유인지 몰라 당황하다가 입력 부분 때문인가 해서 코드를 수정하였다. 입력데이터가 많은 경우 input() 함수를 사용하면 동작 속도가 느려 시간초과로 오답판정을 받을 수 있다. 따라서 이때는 sys 모듈에서 readline() 함수를 이용하여 시간초과를 피해야 한다.
   이 문제에서는 input().split()를 sys.stdin.readline().split()로 대치하여 시간초과를 면하였다.