FIFO Queue 기반 BFS 도입을 통한 Unweighted Graph 최단 경로 보장 및 Stack Overflow 해결

Context

Unweighted Graph 환경에서 최단 경로를 탐색할 때 Naive DFS 채택 시 발생하는 무한 루프와 지수적 시간 복잡도 문제 분석. 특히 대규모 Grid 데이터 처리 시 재귀 호출로 인한 Call Stack Overflow 위험성 존재.

Technical Solution

• FIFO Queue 구조를 활용한 Layer-by-layer 탐색으로 시작점으로부터 동일 거리의 노드를 순차적으로 방문하는 구조 설계
• 방문 노드에 대한 Visited Set 관리로 중복 방문을 차단하여 순환 그래프 내 무한 루프 방지 및 $O(V+E)$ 시간 복잡도 달성
• 재귀 기반의 DFS 대신 Iterative Queue 방식을 도입하여 메모리 스택 제약 없는 안정적인 Grid 탐색 환경 구축
• 상태 기반 탐색(State-based Search)으로 확장하여 특정 조건(예: 장애물 제거 횟수)이 포함된 최단 경로 문제 해결 가능성 확보
• Word Ladder 문제와 같이 단어 간 변환 단계를 Edge로 정의한 Graph 모델링을 통한 최단 변환 시퀀스 도출