깊이 우선 탐색
시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문한다. 최대 깊이 노드까지 방문한 다음에는 이전의 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드를 다시 최대 깊이까지 차례대로 방문한다
탐색을 시작하려면 우선 시작노드를 정하고, 스택에 시작 노드를 푸시한다. 스택에 있는 노드는 아직 방문하지 않았지만 방문할 예정인 노드이다. 시작 노드를 푸시했으면 다음 과정을 반복한다.
진행 1 스택이 비어있는지 확인한다. 스택이 비었다는 건 방문할 수 있는 모든 노드를 방문했음을 의미한다. 따라서 스택이 비어있으면 탐색을 종료한다.
진행 2 스택에서 노드를 팝한다. 팝한 원소는 최근에 스택에 푸시한 노드이다.
진행 3 팝한 노드의 방문 여부를 확인한다. 아직 방문하지 않았다면 노드를 방문 처리 한다.
진행 4 방문한 노드와 인접한 모든 노드를 확인하낟. 그중에서 아직 방문하지 않은 노드를 스택에 푸시한다. 스택은 LIFO 구조이므로 방문 순서를 오름 차순으로 고려한다면 역순으로 노드를 푸시해야 하낟.
이 과정을 코드로 구현할 때 다음 세 가지 사항을 고려해야 한다.
고려 1 탐색할 노드가 없을 때까지 간선을 타고 내려갈 수 있어야 한다.
고려 2 가장 최근에 방문한 노드를 알아야 한다.
고려 3 이미 방문한 노드인지 확인할 수 있어야 한다
깊이 우선 탐색의 핵심은 '가장 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방무할 노드가 있는지 확인한다' 이다.
탐색하고 있는 방향의 역방향으로 되돌아가는 동작을 백트래킹이라고 한다. 스택은 최근에 푸시한 노드를 팝할 수 있으므로 특정 노드를 방문하기 전에 최근 방문 노드를 팝 연산으로 쉽게 확인할 수 있다.
스택을 활용한 깊이 우선 탐색
후입선출의 특성을 가진 스택으로 가장 최근에 방문한 노드를 알 수 있다.
01 단계 스택에는 방문 예정인 노드를 푸시한다. 시작노드는 당연히 방문해야 할 노드이므로 1을 스택에 넣는다. 스택에 푸시한 노드는 초록색, 방문한 노드는 회색으로 칠하도록 하겠다. 아직 1은 방문 하지 않았고 방문 예정이기만 하므로 그래프는 아무것도 칠하지 않았다.
02 단계 이제 1을 방문할 차례이다. 1을 팝한 후에 1이 방문한 상태인지 확인한다. 1은 아직 방문하지 않은 노드이므로 이제 방문처리를 한다(그래프에 회색 칠). 방문처리를 한 후에는 1과 인접하면서 방문하지 않은 노드 4,5를 5->4 순서로 푸시하여 이 후 4->5 순서로 방문처리 할 수 있도록 한다
03 단계 이제 같은 방식으로 팝 푸시를 진행한다. 스택에서 4를 팝한 다음 4가 방문상태인지를 확인한다. 4는 방문하지 않았으므로 방문 처리를 한다. 그런 다음 4와 인접한 2,3을 3->2 순서로 푸시한다
04 단계 2를 팝한다. 2는 방문하지 않았으므로 2를 방문 처리 한다. 그런다음 2와 인접하면서 방문하지 않은 노드 3을 푸시한다.
05 단계 3을 팝하고 방문 처리를 한다. 3과 인접한 노드는 없으니 아무것도 푸시하지 않는다.
06 단계 또 다시 3을 팝할 때 이미 방문 처리 했으므로 아무작업을 하지 않는다.
07 단계 5를 팝하고 5를 방문처리 한다. 스택이 비었으므로 작업이 끝났다.
재귀함수를 이용한 깊이 우선 탐색
재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 깊이 우선 탐색에 활용할 수 있다. 호출할 함수는 dfs()라 선언하고 dfs(N)을 호출하면 다음 동작을 할 수 있다고 가정한다
- dfs(N): N번 노드를 방문처리 하고 N번 노드와 인접한 노드 중 아직 방문하지 않은 노드를 탐색
01 단계 시작 노드는 1번 노드이므로 dfs(1)을 호출한다. dfs(1)이 실행되면 1을 방문처리 하고 내부적으로 dfs(4)를 재귀 호출 한다. 아직 dfs(1)은 dfs(4)를 호출한 상태이므로 종료되지 않는다. 따라서 스택에 dfs(1)이 쌓인다.
02 단계 dfs(4)가 실행되므로 4는 방문처리 하며 내부적으로 dfs(4)는 dfs(2)를 호출한다. 같은 이유로 dfs(4)는 스택에 쌓인다.
03 단계 dfs(2)를 실행한다. 2를 방문처리 하고 dfs(2)는 dfs(3)을 재귀 호출 한다.
04 단계 dfs(3)을 실행한다. 3은 인접 노드가 없으므로 추가로 재귀호출을 하지 않고 함수를 종료한다. 여기서 처음으로 스택에서 빠져나오는 함수가 생긴다.
05 단계 스택 특성에 따라 dfs(2)로 돌아가 다음 실행 스텝을 진행한다. 그러나 2는방문하지 않았으면서 인접한 노드가 없으므로 종료한다.
06 단계 dfs(4)로 돌아가 다음 실행 스텝을 진행한다. 4도 방문하지 않았으면서 인접한 노드가 없으므로 함수를 종료한다. 2의 다음 노드인 3이 인접하지만 3은 이미 방문한 노드이므로 변경된 부분 없이 함수가 종료 된다.
07 단계 dfs(1)의 다음 스탭을 진행한다. 1은 5와 인접해있으므로 dfs(5)를 재귀 호출 한다.
08 단계 dfs(5)를 실행한다. 5를 방문처리하고 5와 인접한 노드가 없으므로 dfs(5)를 종료한다. dfs(1)도 이어 종료한다
너비 우선 탐색
시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다. 여기서 말하는 거리는 시작 노드와 목표 노드까지의 차수이다. 간선 가중치의 합이 아닌 것에 주의한다. 탐색을 하려면 일단 시작 노드를 정하고 큐에 시작 노드를푸시 한다. 시작 노드를 큐에 푸시하면 방문 처리한다. 큐에 있는 노드는 이미 방문처리했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태라고 보면 된다.
진행 1 큐가 비었는지 확인한다. 큐가 비었다면 방문할 수 있는 모든 노드는 방문했다는 의미이다
진행 2 큐에서 노드를 팝한다.
진행 3 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 푸시하며 방문처리 한다.
너비 우선 탐색의 방식을 보면 시작 노드부터 인접한 노드를 모두 방문한 후 그 다음 단계의 인접한 노드를 방문한다. 즉 제일 먼저 발견한 노드를 방문한다. 이러한 특성 때문에 너비 우선 탐색을 진행할 때는 큐를 사용한다.
큐를 이용한 너비 우선 탐색
01 단계 시작 노드를 큐에 푸시하고 방문처리 한다.
02 단계 1을 팝한 후 인접한 4와 5를 본다. 아직 방문하지 않았으므로 방문 처리를 하고 4 5 순서로 큐에 푸시한다.
03 단계 4를 팝한 후 인접한 2와 3을 본다. 아직 방문하지 않았으므로 방문 처리하고 2 3 순서로 큐에 푸시한다.
04 단계 5를 팝한 후 인접한 1과 4를 본다. 이미 방문했으므로 아무것도 하지 않는다. 큐의 나머지 노드들도 자신과 인접한 노드들은 모두 방문했으므로 아무것도 하지 않고 팝한다. 큐가 비면 탐색을 마무리 한 것이다.
깊이 우선 탐색과 너비 우선 탐색 비교
깊이 우선 탐색은 깊게 탐색 후 되돌아오는 특성이 있고, 너비 우선 탐색은 시작 노드에서 인접한 노드부터 방문하는 특성을 가진다.
깊이 탐색 후 되돌아오는 깊이 우선 탐색
깊이 우선 탐색은 가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹하여 최근 방문한 노드부터 다시 탐색을 진행한다는 특징이 있어 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우 활용할 수 있다. 코딩 테스트에서 최단 경로를 찾는 문제가 아니면 깊이 우선 탐색을 고려하는게 좋다.
최단 경로를 보장하는 너비 우선 탐색
너비 우선 탐색은 찾은 노드가 시작 노드로부터 최단 경로임을 보장한다. 왜냐하면 시작 노드로 부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문이다. 너비 우선 탐색은 미로 찾기 문제에서 최단 경로 찾기나 네트워크 분석 문제를 풀 때 활용할 수 있다.
