원하는 데이터를 찾기 위한 탐색 알고리즘 중 '그래프'를 탐색하는 대표적인 방법으로 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)이 있다. 이번 포스트에서는 이 두 가지 탐색법에 대해 알아본다. 이 탐색법은 그래프와 밀접한 관계가 있으므로 이와 관련된 포스트를 먼저 본 뒤에 본 내용을 확인하는 것을 추천한다.
DFS(Depth-First Search)
DFS의 탐색 방법
DFS는 위 그림의 오른쪽에서 보여주듯 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 즉, 그래프를 탐색할 때 특정 경로를 주욱 따라 가장 밑바닥까지 내려간 후 막다른 길에 도착하면 다시 돌아와 다른 경로로 탐색하는 방법이다.
조금 더 자세히 확인해보자. DFS는 탐색에서 하나의 방향을 결정하면 그 방향을 따라 끝까지 탐색을 실시한다. 트리라면 가장 왼쪽의 위치한 노드를 우선적으로 탐색하고, 그래프라면 가중치 또는 별도의 기준을 따라 우선순위를 정하여 탐색할 것이다.
위의 그림을 바탕으로 탐색 순서를 살펴보자.
가장 먼저 0번으로부터 시작하여 왼쪽 끝에 위치한 노드들(1~3)을 먼저 탐색한다. 그리고 막다른 길(3번 노드)에 도착하면 이전 단계(1번 노드)로 돌아가 그 다음 노드(왼쪽으로부터 2번째, 여기서는 링크가 2개이므로 오른쪽 노드인 4번 노드가 된다)를 탐색한다.
4번 노드 역시 막다른 길이므로 이전 단계로 돌아간다. 그런데 이전 단계(1번 노드)의 링크를 모두 확인했으니 다시 그 이전 단계(0번 노드)로 돌아가 다음 노드(2번 노드)를 탐색한다.
이러한 DFS의 탐색 순서를 정리하면 '한 가지 경우를 검증하고, 해당 경우가 틀린 경우라면 이전의 단계로 돌아가는 방식'으로 정리할 수 있다. 그리고 이는 결국 '재귀'와 동일한 형태의 알고리즘이 된다.
DFS의 구현 - 재귀
앞에서 보았던 그래프를 인접 리스트 형태로 구현한 뒤, 각 노드를 방문하면 방문한 노드의 번호를 출력하는 방식으로 DFS를 구현해보자.
graph = [
[1, 2],
[0, 3, 4],
[0, 5, 6],
[1],
[1],
[2],
[2],
]
visited = [False] * 7 # 노드 방문 여부를 확인할 리스트
def dfs(graph, visited, start:int=0):
visited[start] = True # 방문한 노드는 True로 방문 표시
print(f"{start}번 노드를 방문했습니다.")
for i in graph[start]: # v번 노드에 연결된 다른 노드를 순회
if not visited[i]: # 연결된 노드의 값이 False일 경우
dfs(graph, visited, start = i) # 재귀적으로 방문 처리
dfs(graph, visited, 0)
0번 노드를 방문했습니다.
1번 노드를 방문했습니다.
3번 노드를 방문했습니다.
4번 노드를 방문했습니다.
2번 노드를 방문했습니다.
5번 노드를 방문했습니다.
6번 노드를 방문했습니다.그림에서 나타난 순서대로 0 → 1 → 3 → 4 → 2 → 5 → 6번 노드의 순으로 방문했음을 확인할 수 있다.
BFS(Breadth-First Search)
BFS의 탐색 방법
BFS는 그림의 왼쪽과 같이 '인접한 노드'부터 탐색하는 방법이다. 즉, 그래프 탐색 시 가까운 노드들을 우선적으로 방문하고 멀리 있는 노드를 나중에 방문한다. 여기서 '가까이'와 '멀리'의 기준은 '깊이'가 된다.
BFS는 큐를 하나 설정하고 최초 시작 노드를 넣어 방문 처리를 한 뒤, 이를 큐에서 제거하고 해당 노드와 인접한 노드들을 다시 큐에 넣어 방문 처리하는 것을 반복한다. 이때 데이터의 처리는 FIFO(First-In-First-Out)을 적용한다.
BFS의 구현
DFS와 동일한 그래프를 이용해 구현해보자.
from collections import deque
graph = [
[1, 2],
[0, 3, 4],
[0, 5, 6],
[1],
[1],
[2],
[2],
]
visited = [False] * 7 # 노드 방문 여부를 확인할 리스트
def bfs(graph, visited, start:int=0):
queue = deque([start]) # 스택에 최초로 방문한 노드를 삽입
while queue:
v = queue.popleft() # 스택의 왼쪽부터 추출
visited[v] = True
print(f"{v}번 노드를 방문했습니다.")
for i in graph[v]: # 해당 노드와 연결된 노드를 순회
if not visited[i]: # 노드에 방문한 적이 없을 경우 이를 큐에 추가
queue.append(i)
bfs(graph, visited, start=0)0번 노드를 방문했습니다.
1번 노드를 방문했습니다.
2번 노드를 방문했습니다.
3번 노드를 방문했습니다.
4번 노드를 방문했습니다.
5번 노드를 방문했습니다.
6번 노드를 방문했습니다.그림에서와 마찬가지로 1 → 2 → 3 → 4 → 5 → 6의 순으로 순회하는 것을 확인할 수 있다.
DFS와 BFS의 비교 및 적용
| DFS | vs | BFS |
|---|---|---|
| 스택 | 동작 원리 | 큐 |
| 재귀 함수 혹은 스택 | 구현 방법 | 큐 자료구조 |
| 그래프의 깊이가 빠를수록 연산이 빠름 메모리를 적게 사용함 | 장단점 | 찾는 노드가 인접해 있을 때 유리 노드가 많을수록 메모리를 많이 소비함 |
| - 경로의 특징을 저장해야 하는 경우 - 미로 문제 | 문제 적용 | - 최단 거리의 길 찾기 |
참고 자료
관련 코딩테스트 풀이
