[알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS)

 탐색 알고리즘이란 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘이다.

 

 알고리즘의 영역은 그 범위가 매우 넓어서 프로그래밍을 하는 개발자라면 의도하지 않아도 특정 알고리즘을 사용하는 경우가 대부분일 정도이며, 알고리즘의 종류 중에서도 탐색 및 정렬은 가장 많이 사용된다.

 

 그래프의 탐색은 하나의 노드에서 시작해서 모든 노드들을 한 번씩 탐색하는 것이 목적이다. 예를 들면, 특정 장소에서 다른 장소로 갈 수 있는지, 최단 경로를 찾는 경우 등 있다.

 

 그래프의 데이터는 배열처럼 정렬되어있지 않기 때문에 원하는 데이터를 찾기 위해서는 모두 방문해서 찾아야 한다.

 

 

 

 

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

 너비 우선 탐색이란 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 탐색을 진행하다가 더 이상 탐색할 노드가 없을 경우, 그다음 떨어져 있는 노드부터 순서대로 방문한다.

 

 이렇게 너비를 우선적으로 탐색하는 방법을 너비 우선 탐색이라고 하며, 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.

 

 BFS는 그래프 탐색의 경우, 알고리즘을 구현할 때 어떤 노드를 방문했었는지 여부를 반드시 검사해줘야 한다. 검사하지 않을 경우에는 무한루프에 빠질 위험이 있기 때문이다. 따라서, 일반적으로는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있게 큐(queue) 자료구조를 사용한다.

 

 장점으로는 최단 경로가 여러 개인 경우에도 모든 최단 경로가 출력된다는 점과 최단 경로가 존재한다면 깊이가 무한정으로 깊어진다 해도 최단 경로를 찾을 수 있는 점이 있다.

 

 단점으로는 경로가 길어진다면 보다 많은 메모리를 필요로 하게 된다. 또한, 경로를 하나씩 전부 방문하기 때문에 모든 경로를 살펴볼 경우도 존재한다.

 

 

 

 

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

 깊이 우선 탐색이란 임의의 노드에서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색하는 방법으로, 모든 노드 방문하고자 하는 경우에 사용한다. 즉, 넓게 탐색하기 전에 깊게 탐색한다는 것이다.

 

 예시로 미로를 생각해 봤을 때 이해하기가 쉬웠다. 미로를 탐색할 때, 한 방향으로 쭉 가다가 길이 없어지면 다시 갈림길로 돌아와서 다음 길을 쭉 가는 방식으로 진행하므로 깊이 우선 탐식의 방식과 유사하다고 볼 수 있다.

 

 자기 자신을 호출하는 순환 알고리즘의 형태를 갖고 있으며, BFS와 동일하게 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

 

 장점으로는 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용하며, 찾으려는 노드가 깊은 단계에 있는 경우에 BFS보다 빠르게 찾을 수 있다는 점이 있다.

 

 단점으로는 DFS는 해에 도착하면 탐색을 종료하기 때문에 얻어진 해가 최단 경로라는 보장이 없다는 점이 있다.

 

 

 

 

DFS와 BFS의 차이점

 

• DFS는 스택이나 재귀를 사용하고 BFS는 큐를 사용한다.
  
  
• BFS는 재귀적으로 동작하지 않는다.
  
  
• DFS가 더 간단하다.
  
  
• 검색 속도는 BFS가 더 빠르다.
  
  
• 검색 대상의 그래프가 크거나 경로의 특징을 저장해야 하는 경우, 모든 노드를 방문하고자 하는 경우에는 DFS를 사용한다.
• 검색 대상의 규모가 크지 않고 최단 경로를 구하는 경우에는 BFS를 사용한다.