그래프의 탐색 방법, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

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

그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

1. 깊이 우선 탐색 (DFS, Depth-First Search)

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

(출처 https://developer-mac.tistory.com/64)

• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용
• 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색 가능

2. 너비 우선 탐색 (BFS, Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

(출처 https://developer-mac.tistory.com/64)

• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용

3. 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교

(출처 https://namu.wiki/w/BFS)

1) 그래프의 모든 정점을 방문
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다. 두 탐색법 다 모든 노드를 탐색하기 때문이다.

2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다.)

3) 최단거리 구해야 하는 문제
BFS를 쓴다. 왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문이다.

4) 등등

• 검색 대상 그래프가 크다면 DFS를 고려한다. 예를 들어 한국에서 미국까지 가는 경로를 알고 싶은데 BFS로 탐색을 하게 된다면 제일 첫 번째 경로가 미국행이라도 다른 모든 경로를 살펴보아야 한다.
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS