DFS (깊이 우선 탐색)
개념
- Depth-First Search
- 그래프나 트리에서 한 방향으로 최대한 깊이 탐색한 후, 더 이상 갈 수 없으면 뒤로 돌아가서 다른 방향을 탐색하는 알고리즘
- 스택(Stack) 자료구조 또는 재귀(Recursion)를 이용하여 구현
특징
- 후입선출(LIFO) 방식
- 메모리 사용량이 상대적으로 적음
- 목표 노드가 깊은 곳에 있을 때 빠르게 찾을 수 있음
- 해가 없는 경로에 깊이 빠질 위험이 있음
시간 복잡도
- O(V + E) (V: 노드 수, E: 엣지 수)
활용 사례
- 미로 찾기
- 백트래킹 알고리즘
- 위상 정렬
- 사이클 탐지
- 연결 요소 찾기
BFS (너비 우선 탐색)
개념
- Breadth-First Search의 줄임말
- 시작점에서 가까운 노드부터 차례대로 탐색하는 알고리즘
- 큐(Queue) 자료구조를 이용하여 구현
특징
- 선입선출(FIFO) 방식
- 최단 경로를 보장함 (가중치가 없는 그래프에서)
- 메모리 사용량이 상대적으로 많음
- 목표 노드가 시작점과 가까운 곳에 있을 때 빠르게 찾을 수 있음
시간 복잡도
- O(V + E) (V: 정점 수, E: 간선 수)
활용 사례
- 최단 경로 찾기
- 네트워크에서 브로드캐스팅
- GPS 네비게이션
- 웹 크롤링
- 소셜 네트워크에서 친구 추천
비교 및 선택 기준
| 특성 | DFS | BFS |
|---|---|---|
| 자료구조 | 스택 (또는 재귀) | 큐 |
| 메모리 사용량 | 적음 | 많음 |
| 최적해 보장 | X | O (가중치 없는 그래프) |
| 구현 방식 | 재귀적 구현이 간단 | 반복적 구현 |
| 탐색 방향 | 깊이 우선 | 너비 우선 |
언제 DFS를 사용할까?
- 모든 노드를 방문해야 하는 경우
- 메모리가 제한적인 환경
- 백트래킹이 필요한 문제
- 경로의 특성이 중요한 경우
언제 BFS를 사용할까?
- 최단 경로를 찾아야 하는 경우
- 시작점에서 가까운 해를 구하는 경우
- 레벨별 탐색이 필요한 경우
백준 DFS와 BFS
해당 문제는 노드 수(n), 엣지 수(m), 시작 노드 위치(v)를 받고 엣지(m)들을 입력받아 DFS, BFS 수행결과를 출력해야 한다.
graph = [[] for _ in range(n + 1)]
for a, b in m_list:
graph[a].append(b)
graph[b].append(a)- 노드 번호가 1부터 시작하므로 크기를 n+1로 설정(첫번째 인덱스는 사용하지 않는다.)
- 양방향 엣지이므로 a ↔ b 양쪽에 추가
- 입력 받은 엣지 리스트로 각 노드들의 인접 노드 리스트를 만든다.
for i in range(1, n + 1):
graph[i].sort()해당 정렬을 하는 이유는 정렬를 하지 않으면 1번 예제는 통과되지만 2번 예제는 통과되지 않는다.
그 이유는 문제 조건에서 정점 번호가 작은 것을 먼저 방문함으로 → 정렬 필요하다.
import sys
from collections import deque
input = sys.stdin.readline
# dfs 알고리즘
def dfs(graph, v, visited):
# 노드 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드들 재귀적을 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
def bfs(graph, start, visited):
# bfs는 큐를 사용하기 때문에 큐 라이브러리 사용
queue = deque([start])
# 노드 방문 처리
visited[start] = True
# 큐가 빌때까지 반복
while queue:
# 큐에 원소하나를 뽑아 출력 (방문한 곳)
v = queue.popleft()
print(v, end=' ')
# 아직 방문하지 않은 인접 노드들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 입력값
n, m, v = map(int, input().split())
# 간선 리스트 받기
m_list = [list(map(int, input().split())) for _ in range(m)]
# 인접 리스트 초기화
graph = [[] for _ in range(n + 1)]
# 간선 리스트 -> 인접 리스트로 변환
for a, b in m_list:
graph[a].append(b)
graph[b].append(a)
print(graph)
# 인접리스트 정렬
# "정점 번호가 작은 것을 먼저 방문" 조건을 만족하려면 인접 리스트가 정렬되어 있어야 함
for i in range(1, n + 1):
graph[i].sort()
# print(graph)
# dfs visited 초기화
visited_dfs = [False] * (n+1)
dfs(graph, v, visited_dfs)
print()
# bfs visited 초기화
visited_bfs = [False] * (n+1)
bfs(graph, v, visited_bfs)
print()