[Algorithm] BFS, DFS - 너비우선탐색, 깊이우선탐색

BFS와 DFS는 탐색에서 대조적으로 설명하는 대표적인 두가지 방법이다. BFS와 DFS의 중간 그 어딘가에는 Heuristic ( 휴리스틱 ) 함수를 사용한 A* search ( 에이스타 서치 ) 등이 존재한다. 오늘은 BFS와 DFS에 대한 간략한 설명과, 트리구조에서 어떤 방식으로 접근하여 사용하는 지 이야기해보자.

 

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

BFS는 시작점에서 출발하여 종점에 도착할 때 까지 시작점으로부터 같은 거리에 있는 좌표 혹은 노드를 가장 먼저 탐색한다.

 

위 그림에서 왼쪽의 grid는 start로부터 end까지 도달하기 위해 BFS가 동작하는 모습을 단편적으로 보여준다.

마찬가지로 오른쪽의 트리에서 루트로부터 end에 도달할 때까지 거리가 가까운 것부터 먼저 탐색하는 모습을 보여준다.

 

근데, BFS는 이게 전부다.

그렇다면 DFS는 어떨까?

 

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

DFS는 BFS와는 다르게 깊이를 우선하여 탐색한다. 시작점으로부터 점점 깊이 들어가서 원하는 결과를 찾는 방식이다.

 

이렇게 두가지를 간략하게 나타내었지만 여전히 의문이 든다. 그래서 무슨 차이가 있고, 어떤 때에 무엇을 왜쓰는데?

 

쉽게 이해하자.

내가 집안에서만 생활하다가 어딘가에 스마트폰을 두고 어디있는 지 찾고 있다. 솔직히 한 번쯤은 그런 경험이 있지 않을까

 

BFS 방식으로 내 휴대전화를 찾기 위해서는 현재 내가 서 있는 위치로부터 가까운 곳을 먼저 탐색한다.

지금 살고있는 집 구조를 가져왔다

현재 위치로부터 BFS로 탐색을 시작하면 아래처럼 움직이게 된다. ( 너무 이미지가 많아서 gif로 대체한다 )

BFS는 시작위치로부터 가장 가까운 지점을 먼저 탐색한다.

 

그렇다면 DFS는?

한 방향으로 쭈욱 나아간다. 애지간히 깊이 들어갔는데 못찾으면, 시작위치에서 다른 방향으로 다시 출발한다.

 

트리구조의 depth에 따라 ( depth = 0, depth = 1, depth = 2, ... ) 순회하도록 작성할 때에는 BFS ( 너비우선탐색 ) 이 용이하고,

트리구조의 가장 왼쪽 leaf의 값 혹은, 중위탐색 등에 사용하는 것이 DFS ( 깊이우선탐색 ) 이다.