깊이우선탐색
깊이우선 탐색
깊이우선 탐색
깊이우선 탐색(DFS, Depth First Search))이란 문자 그대로 깊이를 우선적으로 추구하는 탐색이다.
길을 갈 수만 있다면 끝까지 깊숙이 가 보고, 거기서 길이 없으면 되돌아오는 방식이다.
그림에서 “노드 A에서 출발해서 노드 F로가능 경로가 존재하느냐?”라는 문제를 풀어보자.
이 문제를 해결하려면 A에서 출발하여 갈 수 있는 모든 곳을 다 가보는 수 밖에 없다.
계속 진행하다 보면 세가지 경우가 나온다.
- 목적지까지 제대로 간다.
- 어떤 도시로 갔는데, 거기서 더 나갈 곳이 없는 막다른 곳이 된다.
- 어떤 길을 따라서 계속 원을 그리며 돈다.
A-B-E-F라는 길을 따라서 1번 결과를 도출했다면 끝이지만 2번 결과처럼 A-G-H를 만나면 더이상 빠져 나갈 곳이 없게 된다. 이른바 막다른길(Dead End)이라고 한다. 그러나 이 경우에 길이 없다고 단정할 수는 없다.
3번은 무한루프로 A-B-C-D-B-C-D경로가 해당된다.
2번 결과를 방지하려면 “막다른 도시라면 다시 바로 그 이전 도시로 되돌아간다”라는 규칙을 정하면 된다. 이를 백트래킹(Backtracking)이라 한다.
3번 결과를 방지하려면 “한번 가본 도시는 다시 안 간다”라는 규칙을 정하면 된다.
이러한 탐색 방법은 스택과 관련이 있다. 어떤 도시를 선택해서 갈 떄마다 그 도시를 스택에 푸시한다면 스택의 내요은 A로부터 출발해서 지금까지 거쳐 온 일련의 도시를 나타낸다.
이렇게 되면 백트래킹은 스택의 팝 작업에 해당한다. 가장 최근에 거쳐 온 도시로 되돌아가는 행위이기 때문이다.
A-B-E-F로 가는 깊이우선 탐색순서이다.
A-B에서 E대신 C를 먼저 탐색한 이유는 인접한 노드가 여럿 있을 때 알파벳 순서로 먼저 방문하도록 규칙을 정했기 때문이다.
만약 맨 끝에 있는 스택이 비어있다면 해당 경로로 가는 길이 없다고 결론지을수 있다.
