Algorithm
BFS (Breadth-First-Search)
- 한국에서 미국으로 가는 비행기를 예약하려고 한다.
- 비행편에 따라 직항과 경유가 있고, 이때 최단 경로를 알아내려면 어떻게 해야 하는지를 알아본다.
- 한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색한다.
- 더는 탐색할 정점이 없을 때, 그 다음 떨어져 있는 정점을 순서대로 방문한다.
- 직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있다.
- 경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있다.
- 위와 같이 너비를 먼저 탐색하는 방법을 BFS 너비 우선 탐색이라고 한다.
- 한 경로를 끝까지 모두 다 탐색하면 처음 발견한 답이 최단 거리가 아닐 수 있지만, BFS는 노드에서 가까운 곳부터 탐색하므로, 경로를 탐색하는 도중 가장 먼저 발견한 해답이 최단거리라는 보장이 있다.
DFS (Depth-First-Search)
- 항공기의 모든 비행편 중 미국에 도착하는 비행편을 알아내고 싶을 때를 알아본다.
- 어떤 비행기가 미국으로 가는 것인지 알 수 없기 때문에 여러 나라를 방문하면서 마지막에 미국에 도착하는 경로를 찾아야 한다.
- 하나의 경로를 끝까지 탐색한 후 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다.
- 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있다.
- 이러한 방법을 깊이 우선 탐색이라고 하며, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.
- 탐색 시간이 조금 오래 걸리지라도 모든 노드를 완전히 탐색할 수 있다.