그래프에서 경로를 탐색할 때 대표적으로 사용하는 방법이 2가지 있다.
1. 깊이 우선 탐색(DFS) : 더 이상 탐색할 노드가 없을 때까지 일단 가본다. 그러다가 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문한다.
2. 너비 우선 탐색(BFS) : 현재 위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어간다. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문한다.
글보다는 이해가 쉬운 그림과 함께 DFS부터 알아보려고 한다.
1. 깊이 우선 탐색 알고리즘 (DFS)
1-1. 깊이 우선 탐색의 탐색 순서
깊이 우선 탐색(Depth-First Search)은 시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문한다. 만약 최대 깊이 노드까지 방문하였다면, 이전에 방문한 노드를 거슬러 올라가면서 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 최대 깊이까지 차례대로 방문한다.
즉 깊이 우선 탐색의 핵심은 다음과 같다.
1. 가장 깊은 노드까지 방문
2. 더 이상 방문할 노드가 없으면
3. 최근 방문한 노드로 돌아온 다음 (백트래킹)
4. 해당 노드에서 방문할 노드 있는지 확인
그림과 설명에서처럼 최근 방문한 노드로 돌아가는 것을 백 트래킹(Back Tracking)이라고 한다. (탐색 방향의 역방향으로 되돌아감)
가장 최근에 방문한 노드를 확인해야 하기에 LIFO의 특징을 가지고 있는 스택(Stack)을 사용해서 구현하는 방법이 있다.
1-1-1. Stack을 활용한 깊이 우선 탐색(DFS)
반면, 스택을 사용하지 않고도 깊이 우선 탐색을 구현하는 방법이 있는데, 바로 재귀 함수를 활용하는 방법이다.
1-1-2. 재귀 함수를 활용한 깊이 우선 탐색(DFS)
재귀 함수를 호출할 때마다 호출한 함수는 콜 스택(Call Stack)이라는 곳에 쌓이므로 깊이 우선 탐색에 활용이 가능하다
호출할 재귀 함수를 dfs()라 선언하고, dfs(N)은 다음과 같은 동작을 하게끔 구현한다.
dfs(N) : N번 노드를 방문 처리하고 N번 노드와 인접한 노드 중 아직 방문하지 않은 노드를 탐색
재귀 함수를 활용한 깊이 우선 탐색의 과정은 다음과 같다.
이와 같이 백트래킹을 스택이나 재귀 함수로 활용하여 깊이 우선 탐색을 구현할 수 있다.
2. 너비 우선 탐색 알고리즘 (BFS)
2-1. 너비 우선 탐색의 탐색 순서
너비 우선 탐색(Breadth-First Search)은 시작 노드와 거리가 가장 가까운 노드를 우선으로 방문하는 방식의 알고리즘이다.
여기에서 거리는 시작 노드와 목표 노드까지의 차수를 의미한다. (가중치의 합이 아닌 것에 주의!)
즉 너비 우선 탐색의 핵심은 다음과 같다.
1. 가장 가까운 노드부터 모두 방문
2. 각 해당 노드에서 방문할 노드 있는지 확인
가장 가까운 노드부터 차례대로 확인해야 하기에 FIFO의 특징을 가지고 있는 큐(Queue)을 사용해서 구현하는 방법이 있다.
Queue을 활용한 너비 우선 탐색(BFS)
3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 비교
깊이 우선 탐색은 깊게 탐색한 후 되돌아오는 특성(백트래킹)이 있으며,
너비 우선 탐색은 시작 노드에서 가장 인접한 노드부터 방문하는 특성을 가진다.
즉 극명하게 다르기에 용도 또한 서로 다르다.
깊이 탐색한 다음 되돌아오는 깊이 우선 탐색 (DFS)
깊이 우선 탐색은 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나
그래프의 사이클을 감지해야 하는 경우 활용할 수 있다.
최단 경로를 보장하는 너비 우선 탐색 (BFS)
너비 우선 탐색은 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문에 최단 경로를 찾는 데에 유리하다.
즉 미로 찾기 문제에서 최단 경로를 찾거나, 네트워크 분석 문제를 풀 때 활용할 수 있다.