BFS와 DFS

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않다. 그래서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.

가장 대표적인 두 가지 방법, BFS와 DFS를 소개한다. 이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.

BFS(Breadth-First Search)

한국에서 미국으로 가는 비행기를 예약하려고 한다. 비행편에 따라 직항과 경유가 있다. 만약 경유하게 된다면, 해당 항공사가 필요로 하는 공항에 잠시 머물렀다가 가기도 합니다. 경유하는 시간은 비행편마다 다르고, 경유지도 다르다. 이렇게 다양한 여정 중에서, 최단 경로를 알아내려면 어떻게 해야 할까?

한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색한다. 그리고 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문한다. 직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있다. 경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있다. 이렇게, 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 한다.

주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 한다!

DFS(Depth-First Search)

그렇다면, 한국에서 출발하는 항공기의 모든 경로 중에 미국에 도착하는 여정을 알아내고 싶을 때에는 어떻게 해야 할까?

비행기 티켓이 없다면 어떤 비행기가 미국으로 가는 것인지 알 수 없다. 이때 비행기를 타고 여러 나라를 방문하면서, 마지막에 미국에 도착하는 경로를 찾아야 한다. DFS는 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다. 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있다. 또 미국으로 가는 길이 아님을 미리 체크할 수 있다면, 바로 그 순간 다음 탐색으로 넘어갈 수 있다.

이렇게, 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 한다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.

DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 사용할 때의 장단점은 분명하기 때문에 해당 상황에 맞는 탐색 기법을 사용해야 한다.