벽 짚기 미로 탈출
한쪽 벽을 계속 짚으며 걷는 미로 탈출법은 DFS와 같은 구조다. 막다른 길에서 되돌아 나와 다음 갈림길을 시도하는 백트래킹이 탐색의 핵심이다.
격자 미로에서 깊이 우선 탐색의 진행과 백트래킹 과정 시각화.
미로를 편집하고 깊이 우선 탐색을 실행해, 스택이 한 방향으로 끝까지 파고들다 막다른 길에서 되감기는 백트래킹과 찾은 경로가 최단이 아닌 이유를 확인합니다.
깊이 우선 탐색은 스택에서 꺼낸 셀에서 갈 수 있는 방향을 하나씩 밀어 넣으며 끝까지 파고든다. 막다른 길에 닿으면 스택을 되감아 다른 분기를 탐색한다. 이렇게 찾은 경로가 최단이라는 보장은 없다.
시간복잡도 O(V + E)
push(neighbors) -> pop -> backtrack on dead end
한쪽 벽을 계속 짚으며 걷는 미로 탈출법은 DFS와 같은 구조다. 막다른 길에서 되돌아 나와 다음 갈림길을 시도하는 백트래킹이 탐색의 핵심이다.
패키지 의존성의 설치 순서 결정과 순환 import 탐지는 DFS의 방문 상태 관리로 푼다. 탐색이 깊어졌다가 되감기는 과정은 함수 콜스택의 동작과 같다.
DFS는 경로가 존재하면 반드시 찾지만 그 경로가 최단이라는 보장은 없다. 같은 미로를 BFS와 비교하면 두 탐색의 차이가 경로 길이로 드러난다.