[BOJ] 11724. 연결 요소의 개수 (Python/DFS/Silver 2)

[Baekjoon] 11724. 연결 요소의 개수

Silver 2 | #DFS #BFS #그래프이론

문제 바로가기 🔗

1. 문제 요약 및 접근 방식

방향 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 문제이다. 즉, 그래프가 몇 개의 독립된 덩어리로 나뉘어 있는지 찾아야 한다.

• 정점 중심 탐색: 간선이 없는 고립된 정점도 하나의 연결 요소로 취급해야 하므로, 모든 정점(1~N)을 순회하며 방문 체크를 해야 한다.
• 인접 리스트 활용: 특정 정점과 연결된 노드들만 효율적으로 탐색하기 위해 인접 행렬보다 인접 리스트를 사용한다.
• 무방향성: 양방향 연결을 위해 graph[u].append(v)와 graph[v].append(u)를 모두 수행한다.

2. 전체 코드 (Python - DFS)

import sys
# 1. 재귀 깊이 설정 (기본값이 낮아 필수적임)
sys.setrecursionlimit(10**6)
# 2. 입력을 빠르게 받기
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
element = 0 # 연결 요소의 개수

# 인접 리스트 생성 (무방향)
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(idx):
    visited[idx] = True
    for i in graph[idx]:
        if not visited[i]:
            dfs(i)

# 모든 정점을 확인하며 탐색 시작
for idx in range(1, N + 1):
    if not visited[idx]:
        element += 1
        dfs(idx)
    
print(element)

3. ✍️ 회고: 시행착오와 언어/알고리즘별 차이

🚫 시간 초과와 간선 중심 탐색의 오류

초기 코드에서는 간선 리스트(graph)를 직접 순회하며 DFS를 시도했다. 하지만 이는 시간 복잡도가 O(M^2)에 달해 시간 초과가 발생했고, 결정적으로 간선이 없는 '고립된 정점'을 카운트하지 못하는 논리적 오류가 있었다. 정점 기준의 인접 리스트로 구현해야 효율성과 정확성을 모두 잡을 수 있음을 배웠다.

---

✔ 과거 기록과의 비교 (C++ & Python BFS)

과거에는 같은 문제를 C++(#110)로 풀었었고, 파이썬으로 풀 때도 BFS(deque)를 주로 활용했었다. 이번에 DFS로 다시 풀며 느낀 차이점은 다음과 같다.

• • C++ vs Python: C++은 메모리 관리가 직접적이지만, 파이썬은 sys.setrecursionlimit 설정이 필수적이라는 점이 가장 큰 차이였다.
• • BFS(과거): 큐를 이용해 한 층씩 탐색하는 방식으로 직관적이지만, 파이썬에서는 deque 모듈 임포트와 큐 관리가 필요하다.
• • DFS(현재): 재귀를 통해 코드가 훨씬 간결해지며, 연결 요소 판별처럼 단순히 모든 연결점을 훑어야 하는 문제에선 DFS가 더 직관적일 수 있음을 체감했다.

---

💡 마무리 포인트

• 파이썬에서 DFS 사용 시 sys.setrecursionlimit은 필수 조건이다.
• 인접 리스트는 무방향 그래프일 때 양쪽 모두에 데이터를 추가해주어야 한다.
• 간선이 아닌 정점의 방문 여부를 체크하는 것이 이 문제의 본질임을 다시 한번 새겼다.

4. 💡 실전 효율성 고민: 왜 BFS가 더 유리할 수 있을까?

이번 문제는 경로의 깊이가 깊어질 수 있는 '연결 요소' 탐색이기에 DFS를 선택했지만, 과거에 BFS(큐)로 풀었던 방식과 비교해 보니 실전 성능 면에서 몇 가지 차이점이 보였다.

• 1. 재귀 오버헤드와 메모리 (Memory)
  DFS는 재귀 호출이 깊어질수록 시스템 스택 메모리를 사용한다. 파이썬에서는 setrecursionlimit으로 강제 설정이 필요하며, 호출 스택이 쌓일수록 메모리 부담이 커질 수 있다. 반면 BFS는 Heap 영역의 큐(Queue)를 사용하므로 상대적으로 메모리 관리에서 자유롭다.
• 2. 시간 복잡도와 안정성 (Time)
  이론상 두 방식 모두 $O(N+M)$이지만, 파이썬의 재귀 함수 호출은 반복문 기반의 while문(BFS)보다 느린 경향이 있다. 데이터가 편향되어 그래프의 깊이가 극단적으로 깊은 경우, DFS는 스택 초과 위험이 있지만 BFS는 안정적으로 모든 노드를 탐색한다.

✅ 최종 결론

"단순히 연결된 덩어리를 찾는 문제라면 Python에서는 BFS가 시간과 메모리 측면에서 조금 더 안전하고 효율적인 선택이 될 수 있다. 하지만 코드의 간결함과 직관적인 구현은 DFS가 우세하므로, 문제의 제약 조건(N, M의 크기)에 따라 유연하게 대처하는 능력이 필요함을 느꼈다."