[알고리즘][개념] DFS(깊이 우선 탐색) & BFS(너비 우선 탐색)
https://devuna.tistory.com/32, 튜나 개발일기를 참고하였습니다.
여러 자료구조 중 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색, DFS와 너비 우선 탐색인 BFS가 존재한다.
여기서 말하는 그래프란 node와 edge로 구성된 자료구조를 말한다. 이 중 방향성이 있는 비순환 그래프를 트리라고 말한다.
이런 그래프를 탐색한다는 의미는 하나의 정점으로부터 시작하여 차례대로 모든 정점을 하나씩 방문하는 것을 의미한다.
코테 문제 중 일부는 이런 search 기법을 잘 구현해야하기에 DFS와 BFS의 개념을 알아보고 python으로 주어진 그래프를 간단히 탐색해보는 예제코드를 작성해보려고 한다.
깊이 우선 탐색(DFS, Depth-First Search)
: 우선 최대한 깊이 내려간 뒤에, 더 이상 갈 수 없다면 옆으로 가자!
깊이 우선 탐색이란 위의 이미지에서 볼 수 있듯이, 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게(깊숙히 끝까지) 탐색하는 방법이다.
스택 또는 재귀함수로 구현한다.
아래의 특징이 있다.
1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
너비 우선 탐색(BFS, Breadth-First Search): 1층 1층 보자..!(layer 단으로 보자)
루트 노드(혹은 다른 임의의 노드)에서 시작해석 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점들, 즉 이웃 노드들을 우선 방문하는 방법이다. 큐를 이용해서 구현한다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
DFS와 BFS 비교
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.
2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
3) 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
이밖에도
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
간단한 코드 구현(python)
트리 구현
class TreeNode:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, node):
self.children.append(node)
# 트리 생성
root = TreeNode(1)
child_1 = TreeNode(2)
child_2 = TreeNode(3)
child_3 = TreeNode(4)
root.add_child(child_1)
root.add_child(child_2)
root.add_child(child_3)
child_1.add_child(TreeNode(5))
child_3.add_child(TreeNode(6))
child_3.add_child(TreeNode(7))
구현된 트리는 아래와 같습니다.
1
/ | \
2 3 4
/ / \
5 6 7DFS 알고리즘:
1. 재귀함수를 이용한 구현
def dfs(node):
if node is None:
return
print(node.value, end=" ") # 현재 노드 출력
for child in node.children:
dfs(child) # 자식 노드에 대해 재귀 호출2. 스택을 이용한 구현
스택의 경우 LIFO를 따름으로 이를 이용. 아래의 방식으로 작동
- 루트 노드를 스택에 추가합니다.
- 스택에서 노드를 꺼내고 그 노드를 방문합니다.
- 꺼낸 노드의 자식들을 스택에 추가하는데, 자식을 오른쪽에서 왼쪽 순서로 넣어야 스택에서 꺼낼 때 왼쪽 자식부터 방문하게 됩니다.
- 스택이 비어있을 때까지 위 과정을 반복합니다.
def dfs_stack(root):
if root is None:
return
stack = [root] # 스택에 루트 노드를 넣음
while stack:
node = stack.pop() # 스택에서 가장 위의 노드를 꺼냄
print(node.value, end=" ") # 현재 노드 출력
# 자식 노드를 스택에 추가 (반대로 추가해야 왼쪽부터 탐색됨)
# 자식들을 오른쪽에서 왼쪽 순으로 스택에 넣어야 왼쪽부터 탐색됨
for child in reversed(node.children):
stack.append(child)
1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7 순서로 탐색함
BFS 알고리즘:
큐를 이용하여 구현. 큐의 경우 FIFO 임으로 탐색할 노드를 큐에 넣고, 이후 그 다음 자식 노드들을 큐에 차례대로 넣어가며 탐색한다.
from collections import deque
def bfs(root):
if root is None:
return
queue = deque([root]) # 큐에 루트 노드를 삽입
while queue:
node = queue.popleft() # 큐의 앞에서 노드를 꺼내고 출력
print(node.value, end=" ")
queue.extend(node.children) # 현재 노드의 자식들을 큐에 삽입
BFS는 트리의 레벨 순서대로 탐색합니다. 먼저 루트 노드 1을 방문하고, 그 다음 레벨에서 2, 3, 4를 방문한 후, 그다음 레벨에서 5, 6, 7을 방문합니다. BFS 탐색 순서는 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7입니다