Unweighted Graph 최단 경로 보장을 위한 O(V+E) BFS 설계 전략

Context

Unweighted Graph에서 최단 경로 탐색 시 Naive DFS 기반의 Brute-force 접근으로 인한 지수적 시간 복잡도 발생. 대규모 Grid 데이터 처리 시 재귀 호출 깊이 제한으로 인한 RecursionError 및 시스템 스택 오버플로우 위험 상존.

Technical Solution

• Queue 기반의 Level-order Traversal을 통한 거리 k의 모든 노드 우선 탐색 구조 설계
• 방문 노드 즉시 마킹을 통한 중복 탐색 제거 및 무한 루프 방지 메커니즘 적용
• Target 노드 최초 발견 시점이 곧 최단 경로임을 보장하는 Layered Expansion 로직 구현
• Explicit Queue 사용을 통한 Call Stack 의존성 제거 및 대규모 맵 데이터 처리 안정성 확보
• 각 정점 및 간선을 최대 1회씩만 처리하는 선형 시간 복잡도 최적화

Impact

• 시간 복잡도: 지수 시간에서 O(V+E)의 선형 시간으로 단축
• 공간 복잡도: O(V) 수준의 Queue 및 Visited Set 메모리 점유

Key Takeaway

가중치가 없는 그래프의 최단 거리 문제 해결 시, 탐색 깊이의 균등 확장을 보장하는 BFS 채택이 설계의 핵심 원칙임.