한국에서 미국으로 가는 비행기를 예약한다고 가정하고 BFS와 DFS를 비교해보자. 비행편에 따라 직항과 경유가 있고 경유를 하게 된다면 해당 항공사가 필요로 하는 공항에 잠시 머물렀다 가기도 한다. 경유를 하는 시간은 비행편마다 다르고, 경유지도 다르다. 이런 경우에 최단 경로를 구하는 방법을 알아보자.
💡BFS (Breadth-First Search)
한국을 기준으로 미국까지는 가는 방법을 정점부터 탐색한다. 그리고 더는 탐색할 정저이 없을때, 그 다음 떨어져 있는 정점을 순서대로 방문한다. 직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있다. 경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있다. 이렇게 너비를 우선적으로 탐색하는 방법을, BFS, Breadth-First Search, 너비 우선 탐색이라고 한다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다.
💡 DFS (Depth-First Search)
비행기 티켓이 없다면 어떤 비행기가 미국으로 가는지 알 수 없다. 비행기를 타고 여러 나라를 방문하면서, 마지막에 도착하는 경로를 찾아야한다. DFS 는 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다. 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있다. 또 미국으로 가는 길이 아님을 미리 체크할 수 있다면 그 다음으로 바로 넘어갈 수 도 있다. 이렇게 깊이를 우선적으로 탐ㅁ색하는 방법이 DFS, Depth-First Search, 깊이 우선 탐색이라고 한다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.
댓글