DFS란?
DFS(Depth-First Search, 깊이 우선 탐색)는 트리 또는 그래프에서 한 경로를 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 다시 이전 단계로 돌아가서 다른 경로를 탐색하는 알고리즘이다.
DFS는 재귀 혹은 스택을 통해 구현되며, 노드 간의 깊은 관계를 파악할 때 유용하다.
DFS의 작동 원리
- 시작 노드 선택: 탐색을 시작할 노드를 하나 정한다.
- 방문 처리: 현재 노드를 방문했다고 표시한다.
- 재귀적 탐색: 인접한 노드 중 방문하지 않은 노드가 있으면 그 노드를 기준으로 다시 DFS를 실행한다.
- 되돌아오기: 더 이상 탐색할 노드가 없으면 이전 단계로 돌아간다.
DFS의 특징
- 재귀적 구현 또는 명시적 스택 사용이 일반적이다.
- 탐색 순서는 깊이 우선, 즉 한 방향으로 쭉 뻗는다.
- 그래프 탐색, 미로 찾기, 백트래킹 전처리 등에 자주 쓰인다.
- 방문 여부를 체크하지 않으면 무한 루프가 발생할 수 있다.
DFS 핵심 코드 (Python)
def dfs(node):
visited[node] = True
for next_node in graph[node]:
if not visited[next_node]:
dfs(next_node)BFS란?
BFS(Breadth-First Search, 너비 우선 탐색)는 트리 또는 그래프에서 가까운 노드부터 먼저 탐색하는 알고리즘이다.
BFS는 큐(Queue)를 이용해서 구현되며, 시작점에서 각 노드까지의 최단 거리를 구하는 데 유용하다.
BFS의 작동 원리
- 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 하나 꺼내서, 해당 노드와 인접한 모든 노드 중 방문하지 않은 노드를 큐에 삽입하고 방문 처리한다.
- 큐가 빌 때까지 반복한다.
BFS의 특징
- 최단 거리 탐색에 유용하다.
- 큐(Queue)를 사용하며 반복문으로 구현한다.
- Flood Fill, 최소 이동 횟수, 그래프 연결 요소 파악 등에 활용한다.
- 메모리를 많이 사용하므로 그래프 크기가 클 경우 주의해야 한다.
BFS 핵심 코드 (Python)
from collections import deque
def bfs(start):
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
for next_node in graph[node]:
if not visited[next_node]:
visited[next_node] = True
queue.append(next_node)DFS vs BFS vs 백트래킹 | 언제 어떻게 쓸까
| 알고리즘 | 구현 방식 | 특징 | 활용 예시 |
|---|---|---|---|
| DFS | 재귀 / 스택 | 깊이 우선 탐색, 경로 추적에 유리 | 미로 탐색, 그래프 연결 요소 탐색 |
| BFS | 큐 | 너비 우선 탐색, 최단 거리 탐색에 유리 | 최단 경로, 레벨별 탐색 |
| 백트래킹 | 재귀 + 가지치기 | 유망하지 않으면 탐색 중단, 조합 탐색 | 순열/조합, N-Queen, 스도쿠 |
