[알고리즘] 깊이우선탐색(DFS)과 너비우선탐색(BFS)
1. 깊이 우선 탐색(Depth-First Search)
: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동(백트랙이라고도 불림)
- 재귀를 사용하는 경우가 많음
- 오델로, 장기, 바둑 등 대전형 게임에 필수로 사용
- 모든 답을 찾지 않고 정해진 깊이까지 탐색하는 방법도 자주 사용됨
- 너비 우선 탐색에 비해 메모리 사용량을 줄일 수 있음
1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
DFS는 스택이라는 자료구조를 활용해서 구현된다. 스택은 LIFO(Last-In-First-Out) 방식을 사용한다. (후입선출)
DFS 알고리즘은 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로를 탐색하는 알고리즘이다. 이 때 경로를 탐색하다 동일한 깊이의 인접한 노드가 여러개 있다면 이 중 노드의 번호가 작은 것부터 차례대로 탐색하는 것이 관행이라고도 한다.
파이썬 코드 구현
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []]
data = [0]
def search(pos):
print(pos, end = ' ')
for i in tree[pos]:
search(i)
search(0)
--------------------------------------------------------------------------
0 1 3 7 8 4 9 10 2 5 11 12 6 13 14
2. 너비 우선 탐색(Breath-First Search)
탐색을 시작하는 곳에서부터 가까운 것을 나열하고 자세히 조사해나가는 방법
너비 우선 탐색은 가장 가까운 노드부터 탐색하는 알고리즘이다. (DFS는 최대한 깊은 부분을 탐색하여 가장 멀리 있는 노드를 우선으로 탐색한다는 점에서 차이가 있다.)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택
BFS는 큐라는 자료구조를 사용한다. 큐는 FIFO(First-In-First-Out) 방식을 사용한다. 즉, 큐에 데이터를 넣을 때 순서와 큐에서 데이터를 뺄 때 순서가 동일하다. BFS도 만약 동일한 깊이의 노드가 여러개 있다면 큐에 노드에 새겨진 숫자가 작은 노드들부터 삽입한다.
BFS를 Python으로 구현하기 위해서는 큐를 사용해야 한다. Python에서는 collections 라이브러리가 제공하는 deque 메소드를 사용하면 된다.
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []]
data = [0]
while len(data) > 0:
pos = data.pop(0)
print(pos, end = ' ')
for i in tree[pos]:
data.append(i)
--------------------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
3. DFS vs BFS
| DFS(깊이우선탐색) | BFS(너비우선탐색) |
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
출처