DFS (깊이 우선 탐색, Depth-First Search)
DFS는 최대한 깊이 들어간 후 더 이상 갈 곳이 없으면 되돌아오는 방식으로 탐색하는 알고리즘이다.
보통 재귀 함수 또는 스택을 사용해서 구현한다.
DFS 동작 과정
- 시작 노드에서 출발하여 한 방향으로 최대한 이동한다.
- 더 이상 갈 곳이 없으면 이전 노드로 돌아가 다른 경로를 탐색한다.
- 모든 노드를 방문할 때까지 위의 과정을 반복한다.
DFS 코드 예제
def dfs(graph, node, visited):
visited[node] = True
print(node, end=' ') # 방문한 노드 출력
for neighbor in graph[node]:
if not visited[neighbor]: # 방문하지 않은 노드라면
dfs(graph, neighbor, visited)
# 그래프 (인접 리스트)
graph = {
1: [2, 3, 4],
2: [5, 6],
3: [7],
4: [],
5: [],
6: [],
7: []
}
visited = {key: False for key in graph} # 방문 여부 저장
dfs(graph, 1, visited) # 1번 노드부터 DFS 시작
DFS 특징
✅ 깊이 우선 탐색이므로 특정 경로를 찾거나, 모든 경우를 탐색하는 데 유용하다.
✅ 스택 또는 재귀를 활용하여 구현한다.
✅ 백트래킹(Backtracking)과 같이 활용되며, 예를 들어 미로 탐색 문제 해결에 적합하다.
❌ 경우에 따라 스택 오버플로우가 발생할 수 있음 (너무 깊이 탐색할 경우).
❌ 최단 경로를 보장하지 않음 (DFS는 깊이 우선이므로 경로가 길어질 수 있다).
BFS (너비 우선 탐색, Breadth-First Search)
BFS는 가까운 노드부터 탐색하는 방식의 알고리즘이다.
보통 큐(Queue) 를 사용해서 구현한다.
BFS 동작 과정
- 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼내고, 해당 노드의 인접한 노드들을 큐에 넣는다.
- 위의 과정을 큐가 빌 때까지 반복한다.
BFS 코드 예제
from collections import deque
def bfs(graph, start):
visited = {key: False for key in graph} # 방문 여부 저장
queue = deque([start]) # 큐에 시작 노드 추가
visited[start] = True
while queue:
node = queue.popleft() # 큐에서 하나 꺼냄
print(node, end=' ')
for neighbor in graph[node]:
if not visited[neighbor]:
queue.append(neighbor) # 큐에 추가
visited[neighbor] = True
# 그래프 (인접 리스트)
graph = {
1: [2, 3, 4],
2: [5, 6],
3: [7],
4: [],
5: [],
6: [],
7: []
}
bfs(graph, 1) # 1번 노드부터 BFS 시작
BFS 특징
✅ 최단 경로를 보장 (같은 깊이의 노드를 먼저 탐색하기 때문).
✅ 큐(Queue)를 이용해 구현하여 직관적이고 코드가 깔끔하다.
✅ 모든 노드를 한 번씩 방문하는 경우에 유리.
❌ 메모리를 많이 사용 (모든 노드를 저장하는 큐가 필요하므로).
❌ 경우에 따라 속도가 느릴 수도 있음 (너무 많은 노드를 탐색해야 하는 경우).
언제 DFS, BFS를 사용해야 할까?
🔹 DFS를 사용해야 할 경우
- 백트래킹(Backtracking): 최적의 해를 찾거나, 모든 경우의 수를 탐색할 때 (예: 미로 탐색, 조합 문제).
- 재귀적으로 탐색이 필요한 경우: 그래프 탐색이나 깊이 있는 탐색이 필요한 문제.
- 경로를 찾는 문제에서 모든 가능성을 탐색해야 하는 경우.
🔹 BFS를 사용해야 할 경우
- 최단 경로 탐색: 가중치가 없는 그래프에서 최단 경로를 구할 때.
- 모든 노드를 같은 깊이에서 탐색해야 할 때: 예를 들어, 네트워크 연결 상태 확인.
- 탐색해야 하는 노드가 많지만, 탐색 깊이가 얕을 때: DFS보다 BFS가 빠름.
예제 문제 추천 (백준)
- DFS 연습 문제
- 📌 백준 2606번 - 바이러스
- 📌 백준 1012번 - 유기농 배추
- 📌 백준 11724번 - 연결 요소의 개수
- BFS 연습 문제
- 📌 백준 2178번 - 미로 탐색
- 📌 백준 7576번 - 토마토
- 📌 백준 1697번 - 숨바꼭질
코딩 테스트에서는 보통 BFS가 더 많이 사용되지만, DFS와 함께 백트래킹을 활용하는 문제도 많으니 둘 다 확실하게 익히는 것이 중요하다
