BFS 와 DFS

탐색 알고리즘에는 여러가지가 있습니다. 가장 기본적인 알고리즘이 BFS 와 DFS 인데요. 각각 아래에서 살펴보겠습니다.

BFS(Breath First Search)

BFS 는 너비우선탐색 알고리즘입니다. 위의 트리는 깊이(depth)가 2인 이진트리입니다. BFS는 루트부터 시작해서 깊이별로 가로방향을 먼저 탐색해나가는 방식입니다. 따라서 1단계에 있는 a를 먼저 탐색하고, 2단계에 있는 b,c 를 탐색하고, 마지막으로 3단계에 있는 d,e,f,g 를 탐색하는 방식입니다. 

• 장점
1. 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장합니다.
2. 최단경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있습니다.
3. 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리합니다.
• 단점
1. 재귀호출을 사용하는 DFS 와는 달리 큐를 이용해 다음에 탐색할 노드들을 저장하기 때문에 노드의 수가 많을수록 필요없는 노드들까지 저장해야하기 때문에 더 큰 저장공간이 필요합니다.
2. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기 때문에 비현실적입니다.

BFS를 이용해 탐색을 할 경우, 평균 탐색 노드의 수는 다음과 같습니다. (b: 가지수, d : 깊이)

• 평균 탐색 노드의 수 = ( d - 1 깊이까지의 총 노드 수 ) + ( d 깊이에서의 평균 노드 수 )
• ( d - 1 깊이까지의 총 노드 수 ) = 1 + b + b^2 + ... + b^(d-1) = (b^d -1) / (b-1)  →  위의 예제에서는 1 + 2 = 3 입니다.
• ( d 깊이에서의 평균 노드 수 ) = (최우측일 경우 탐색 수 + 최좌측일 경우 탐색 수 ) / 2 = (1 + b^d) / 2  →  위의 예제에서는 (1 + 4) / 2 입니다. 
• 따라서 평균 탐색 노드의 수는 (b^d -1) / (b-1) + (1 + b^d) / 2 입니다.

BFS는 큐를 이용하기 때문에 큐로 설명을 드리자면, 큐에 a를 넣습니다. 이후 작업은 while 문으로 큐의 길이가 0보다 크면 무한히 수행합니다. 반복문을 실행해 큐에 있는 노드들을 하나씩 꺼내 그 노드의 자식이 존재한다면 모두 큐에 넣고 자식이 없다면 최단경로로 인지하시면 됩니다. 

DFS(Depth First Search)

DFS는 깊이우선탐색 알고리즘입니다. BFS와 같은 트리로 살펴보겠습니다. DFS는 하나의 노드를 탐색하면 그 자식들을 모조리 탐색하는 방식입니다. 깊게 파고드는 것이죠. 따라서 위의 트리에서보시면 a 를 탐색하고, b를 탐색, d를 탐색하고 자식이 없으면 한 단계 이전으로 돌아가 b의 다른 자식인 e를 탐색합니다. 이 방식을 백트랭킹(back-tracking) 이라고 합니다. e 의 자식이 존재하지 않으므로 백트랭킹해 b로, b의 또다른 자식이 존재하지 않으므로 a로 돌아가 다른자식인 c를 탐색합니다. DFS를 길찾기 용도로 사용한다면 모든 경로를 다 살펴본 후에야 최단경로를 알 수 있습니다. a → b → d 가 최단경로여도 그 이후에 최단경로가 나올 수도 있기 때문에 a → c → g 경로까지 살펴봐야하는 것입니다.

• 장점
1. BFS에 비해 저장공간의 필요성이 적습니다. 백트랙킹을 해야하는 노드들만 저장해주면 됩니다.
2. 찾아야하는 노드가 깊은 단계에 있을수록, 그 노드가 좌측에 있을수록 BFS 보다 유리합니다.
• 단점
1. 답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠질 우려가 있습니다.
2. 위에서도 설명드렸듯이, 내가 지금까지 찾은 최단경로가 끝까지 탐색했을 때의 최단경로가 된다는 보장이 없습니다.

DFS를 이용해 탐색을 할 경우, 평균 탐색 노드의 수는 다음과 같습니다. (b: 가지수, d : 깊이)

• 평균 탐색 노드의 수 = { ( 목표 노드가 최좌측에 있는 경우의 탐색 수 ) + ( 목표 노드가 최우측에 있는 경우의 탐색 수 ) } / 2
• ( 목표 노드가 최좌측에 있는 경우의 탐색 수 ) = (루트노드 + 깊이) = 1 + d   →  위의 예제에서는 1 + 2 = 3 입니다.
• ( 목표 노드가 최우측에 있는 경우의 탐색 수 ) = 1 + b + b^2 + ... + b^d = (b^(d+1) - 1)(b - 1)  →  위의 예제에서는 (2^3 + 1) / 1 = 7  입니다. 
• 따라서 평균 탐색 노드의 수는 { (1 + d) + (b^(d+1) - 1)(b - 1) } / 2 입니다.

두 알고리즘을 사용하실 때는 본인의 탐색 또는 길 찾기의 경우에 어떤 알고리즘이 더 효율적인지를 생각해 사용하셔야 됩니다 :)