[Algorithm] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)은 코딩 테스트에서 단골로 출제되는 문제 유형 중 하나다. 

 

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

DFS는 최대한 깊이 먼저 내려간 후, 더 이상 나아갈 곳이 없는 경우에 옆으로 이동하여 다시 탐색하는 방식이다. 

 

0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 의 형태로 움직이는 것이다. 미로 찾기 등과 같은 문제를 해결할 때 한 방향으로 끝까지 갈 수 있을 때까지 간 후, 더 이상 갈 수 없으면 가장 가까운 갈림길로 돌아와서 해당 갈림길 방향으로 다시 탐색하는 방식으로 볼 수 있다. 모든 경우의 수를 탐색하고자 할 때 DFS를 사용한다. 그러나, 모든 경우의 수를 다 탐색해야 하기 때문에 BFS 보다 속도는 느리다. DFS는 주로 스택 또는 재귀함수로 구현한다. 

 

 

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

BFS는 너비 우선 탐색 방식으로, 특정 노드에서 시작해서 인접한 노르르 먼저 탐색하는 방식으로, 시작 지점으로부터 가까운 곳을 먼저 탐색하고 먼 곳에 있는 지점이 가장 나중에 방문하는 방법이다. 주로, 두 지점 간의 최단 경로를 찾고 싶을 때 많이 사용한다. BFS 방식은 주로 큐를 사용하여 문제를 푼다. 

 

 

DFS와 BFS는 문제에 따라 다르며, 각 방법을 사용할 때 적절한 문제가 있고, 둘다 사용해도 상관없는 문제도 있다. 모든 지점을 방문해야 되는 경우에는 DFS, BFS 둘다 사용해도 되고, 각 경로에 대한 제한 사항이 있는 경우에는 DFS를 주로 사용한다. 반면에, 최단 거리를 구하는 문제의 경우에는 주로 시작 지점에서 가까운 곳으로 탐색하는 방식인 BFS를 사용한다.