넓이 우선 탐색(BFS) vs 깊이 우선 탐색(DFS)
Introduction
넓이 우선 탐색 (BFS) 와 깊이 우선 탐색 (DFS) 이란 각각 무엇인지,
코딩 테스트 문제를 풀 때 BFS, DFS 둘 중 어느 것을 이용할지 정리해보겠습니다.
넓이 우선 탐색 ( BFS , Breadth-First Search )
루트 노드(혹은 임의의 노드)에서 시작해 인접한 노드먼저 탐색합니다. 시작 노드부터 가까운 노드를 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 방식을 말합니다.
인접한 노드(2,3,4)를 받아오고 그 노드들(3,4)에 대해서 먼저 처리하기 때문에 선입 선출 (First In First Out) 구조인 Queue 를 이용합니다.
깊이 우선 탐색 ( DFS, Depth-First Search )
루트 노드 (혹은 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다. 즉, 한 branch에서 최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없으면 다른 branch 탐색합니다.
인접한 노드(2,6,8) 를 받아오지만, 인접한 노드보다 한 branch에 있는 노드들(3,4)을 먼저 처리하기 때문에 선입 후출 (First In Last Out) 구조 또는 후입 선출(Last in First Out)구조인 Stack과 재귀함수를 이용합니다.
BFS vs DFS
- 공통점
- 모두 방문한 node를 표시해주어야 합니다. 그렇지 않을 경우 무한으로 순환할 수 있습니다.
- 방문한 node를 표시해주는 방법
- 2차원 배열 경우에 방문한 좌표 x,y에 해당하는 graph[x][y] 를 바꿉니다.(1차원 배열 같은 경우도 동일)
- node에 방문했는지 check하는 자료( list, set, dictionary )를 만들어 그 node의 방문 여부를 True False 같이 binary로 표현하거나 방문 안했을 때는 -1 방문했을 때는 그 node까지의 거리 같은 값을 넣어 해당 node의 방문 여부를 표현합니다.
- 차이점
| BFS | DFS | |
| 탐색 방법 | 루트 노드 (혹은 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색 | 루트 노드(혹은 임의의 노드)에서 시작해 인접한 노드먼저 탐색. 시작 노드부터 가까운 노드를 방문하고 멀리 떨어져 있는 노드를 나중에 방문 |
| 구현 방법 | Queue | Stack, 재귀함수 |
| 탐색 속도 | 빠름 | 느림 |
| 사용 시기 | 최단 거리 및 경로(각 node간 거리 =1인 경우) | 각각 경로마다의 특징이 있을 때(BFS로는 안됨) |
