[자료구조] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

탐색에 대해 이해하려면 트리 구조를 먼저 살펴보는 것이 좋다.

 

트리(tree)는 나무가 가지치는 것처럼 생긴 "그래프"의 일종이다.

방향성(보통 위에서 아래)이 있는 비순환 그래프라고도 말하며, 루트 노드(최상위 노드), 부모-자식간의 노드 등이 존재한다.

여기서 말하는 노드는 정점이라고도 말하는데 특정 장소를 생각하면 된다. 이런 노드를 연결하는 것을 엣지(간선)이라 부르는데, 장소를 잇는 도로라고 생각하면 쉽다.

 

보통 트리는 다음과 같이 생긴 것을 의미한다.

노란 원이 노드, 파란 선이 엣지이다

이런 트리도 여러가지 조건 등을 붙이면서 특이한 종류의 트리를 만들 수 있는데, 우선 이 포스트에서는 그 것이 중점이 아니므로 깊게 다루지는 않을 것이다. (언젠가 다른 게시물에서 다룰 예정이다.)

 

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

DFS는 말 그대로 깊은 것을 우선 해서 탐색하는 기법이다. 위와 같은 트리가 있다고 가정하자. 깊이를 우선시 하는 탐색 기법이기 때문에 탐색의 순서는 위 그림에 적힌 번호대로 될 것이다. 

 

일반적으로 가장 상위에 있는 노드를 루트 노드라고 부르고 그 노드 부터 탐색을 하게 된다. 깊은 것을 먼저 탐색하기 때문에 2다음 5가 아니라 그 하위에 있는 3번 노드로 갈 것이다. 왼쪽, 오른쪽 중에 어느 것을 먼저 갈 것인가는 탐색하는 사람의 마음이지만, 일반적으로는 왼쪽을 먼저 탐색한다.

 

정리하자면 계속 내려가면서 탐색하다가, 더 이상 내려갈 곳이 없으면 본인의 형제 노드, 형제 노드가 없다면 상위로 올라가서 상위의 형제 노드를 탐색하는 식이다.

 

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

BFS는 DFS와는 다르게 자식 노드(하위 노드) 보다 형제 노드(같은 레벨에 있는 노드)를 먼저 탐색하는 것을 말한다. 같은 트리를 BFS로 탐색한다면 위 그림의 순서 처럼 탐색하게 된다.

 

현재 나와 같은 레벨에 있는 노드(형제 노드)들을 다 탐색했다면, 그제서야 다시 돌아와서 하위 노드를 탐색하는 순이다.

DFS와 마찬가지로 오른쪽, 왼쪽은 코드 짜는 사람 마음이지만, 일반적으론 왼쪽 먼저 탐색한다. 

---

두 가지 방법 중에 더 효율적인 방법은 딱히 없다. 내가 탐색하고자 하는 것에 따라 매번 달라지기 때문이다. 예를 들어 B가장 오른쪽에 있는 노드가 내가 찾아야 하는 노드였다면, DFS로는 5번째에, BFS는 3번째에 찾아져서 이 경우는 BFS가 유리하지만, 또 가장 왼쪽 아래에 있는 노드를 찾아야 했던거라면 DFS로는 3번째, BFS는 4번째에 찾아지기 때문이다.

문제 상황에 가장 적합한 방식을 골라 문제를 해결하면 된다.

 

대표적으로는 다음과 같은 문제가 있다

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

제일 기본적인 DFS, BFS를 묻는 문제이다.

참고로 이에 대한 해설은 다음 게시물에 업로드 할 예정이다.