깊이 우선 탐색(DFS), 스택과의 관계

깊이우선 탐색이란?
그래프를 탐색할 때, 현재 위치에 인접한 노드를 우선적으로 선택하여 깊이가 증가하는 방향으로 탐색하는 알고리즘.
출처: 네이버 지식백과

깊이우선 탐색의 종류

전위, 중위, 후위 순회
좌, 우 순서는 고정하고 부모노드의 방문 우선순위에 따라 종류가 갈린다.
좌, 우의 우선순위에 해당할 경우 이동을 한다. 부모 노드의 우선순위에 도달할 경우 출력한다.

1. 전위순회: 부모, 좌, 우
2. 중위순회: 좌, 부모, 우
3. 후위순회: 좌, 우, 부모

이진 트리에서의 깊이 우선 탐색

1. 전위순회: 1 → 2 → 4 → 5 → 3 → 6 → 7
2. 중위순회: 4 → 2 → 5 → 1 → 6 → 3 → 7
3. 후위순회: 4 → 5 → 2 → 6 → 7 → 3 → 1

스택과의 관계 - 재귀

깊이를 우선하며 방문한 노드를 스택에 저장하며 가장 마지막으로 기록된 노드에 대해 탐색을 수행한다. 더 이상 탐색이 불가능한 경우 노드를 스택에서 제거(pop)하여 이전 노드로 돌아간다.
구현시, 재귀를 이용하면 스택 프레임에 각 메소드를 스택 자료구조로 저장해두기 때문에, 따로 스택을 이용해 구현하지 않아도 된다.

깊이 우선 탐색의 특징

• 복잡한 구조를 탐색하는데 효과적인 성능을 보인다.
• 모든 상태를 탐색하여 최적의 해를 찾는 문제에서 활용 가능하다.

깊이 우선 탐색을 적용할만한 문제

1. 미로찾기: 한쪽 길로 진행하다가 더 이상 진행이 불가능할 경우 직전의 갈림길로 돌아와 다른 방향의 길을 탐색.
2. N-Queen 문제.

깊이 우선 탐색의 단점

• 한 뱡향으로 최대한 깊게 탐색하기 때문에, 탐색 경로가 무한히 길어질 수 있는 문제에서는 탐색이 끝나지 않을 수 있다. 이를 개선하기 위해서는 노드의 방문여부를 기록해 방문 수를 줄일 수 있다.
• 최단 경로를 찾는 문제에도 적합하지 않을 수 있다. 목표점까지의 최단경로를 발견한 후에도 나머지 경로를 모두 확인하며 갱신될 여지가 있기 때문이다.