그래프 탐색 알고리즘
그래프(Graph):
정점(Vertex)과 간선(Edge)을 이용해 여러 대상의 연결 관계를 표현한 자료구조
탐색(Traversal/Search):
그래프의 정점들을 일정한 순서로 방문하며 원하는 정보나 경로를 찾는 과정
대표 활용:
경로 탐색
네트워크 탐색
연결 요소 확인
상태 공간/경우의 수 탐색
DFS
Depth-First Search, 깊이 우선 탐색
ex) 드라마 하나를 몰아서 끝까지 보기
“한 방향으로 갈 수 있는 데까지 깊게 간다.”
구현:
- 재귀 함수
- 스택
일반적인 인접 리스트 그래프 탐색의 시간복잡도:
O(V + E)- V: 정점 수
- E: 간선 수
특징:
- 한 경로를 최대한 깊게 탐색한 후 더 이상 갈 곳이 없으면 이전 정점으로 돌아감
- 처음 발견한 경로가 최단 경로라는 보장은 없음
- 조합, 순열, 백트래킹 등 경우의 수 탐색에 DFS를 사용할 경우 탐색 공간이 매우 커질 수 있음
BFS
Breadth-First Search, 너비 우선 탐색
ex) 여러 드라마를 1편씩 번갈아 보기
“현재 위치에서 가까운 정점부터 넓게 탐색한다.”
구현:
- 큐(Queue) 사용
- Python에서는 보통 collections.deque 사용
- 큐는 연결리스트나 deque 등으로 구현
일반적인 인접 리스트 그래프 탐색의 시간복잡도:
O(V + E)
→ 따라서 일반적인 그래프 전체 탐색에서 BFS가 DFS보다 시간복잡도가 낮은 것은 아니다.
BFS와 최단거리
BFS는:
거리 0
→ 거리 1
→ 거리 2
→ 거리 3처럼 시작점에서 가까운 정점부터 레벨 단위로 탐색
FIFO 큐를 사용하기 때문에 앞선 레벨의 정점들이 다음 레벨보다 먼저 처리.
따라서 가중치가 없는 그래프에서는 시작점으로부터 어떤 정점에 처음 도달했을 때 그 경로의 간선 수가 최단거리임을 보장할 수 있음
중요한 것은 같은 레벨의 정점들끼리의 정확한 순서가 아니라
최단 경로 보장 시 레벨 순서의 유지가 중요.
→ 거리 1의 정점들을 거리 2의 정점들보다 먼저 처리하는 것
방문 체크(visited)는 이미 확인한 정점을 다시 큐에 넣는 것을 막아 중복 탐색을 방지한다.
BFS의 기본 흐름:
시작 정점을 큐에 넣음
→ 큐의 맨 앞 정점을 꺼냄
→ 해당 정점의 이웃을 확인
→ 방문하지 않은 이웃을 큐에 추가
→ 큐가 빌 때까지 반복배열/격자 문제에서는 상하좌우 등의 방향 정보를 이용해 시작점에서 범위를 넓혀가며 탐색하는 형태로 많이 사용한다.
DFS와 BFS의 차이
| 구분 | DFS | BFS |
|---|---|---|
| 탐색 방식 | 한 방향으로 깊게 | 가까운 곳부터 넓게 |
| 구현 | 재귀 / 스택 | 큐 |
| 시간복잡도 | O(V+E) | O(V+E) |
| 최단거리 | 보장하지 않음 | 무가중치 그래프에서 보장 |
| 특징 | 깊은 탐색, 백트래킹과 자주 사용 | 레벨 단위 탐색 |
Q1. 무한히 깊어지는 경로가 있다면?
여러 갈래 중 한 경로가 무한히 깊어지고, 목표가 다른 유한 깊이의 경로에 있다고 하자.
DFS는 특정 경로를 계속 깊게 탐색하므로 무한한 경로에 빠지면 목표를 찾지 못할 수 있다.
반면 BFS는:
깊이 0
→ 깊이 1
→ 깊이 2
→ ...순서로 탐색하므로 목표가 유한한 깊이에 존재한다면 도달할 수 있다.
단, 각 깊이에서 탐색해야 하는 정점 수가 유한하다는 등의 조건이 필요하다.
Q2. 같은 거리의 정점이 여러 개라면?
ex)
graph = {
0: [1, 2, 3]
}BFS에서:
for i in graph[current]:
queue.append(i)이면 인접 리스트의 순서대로:
1 → 2 → 3
가 큐에 들어간다.
FIFO이므로 먼저 들어온 정점부터 처리한다.
DFS의 재귀 구현도:
for i in graph[start]:
dfs(graph, i, visited)처럼 인접 리스트의 앞쪽 정점부터 깊게 들어간다.
따라서:
0: [1, 2]이면 보통 1을 먼저 탐색하고,
0: [2, 1]이면 2를 먼저 탐색한다.
즉:
같은 깊이/거리의 정점이 여러 개라면 인접 리스트에 저장된 순서가 방문 순서에 영향을 줄 수 있다.
문제에서 “정점 번호가 작은 순서대로 방문” 같은 조건이 있다면 인접 리스트를 정렬해서 사용하기도 한다.
Q3. DFS/BFS는 완전 탐색인가?
DFS/BFS는 완전 탐색을 구현하는 데 사용할 수 있는 탐색 방식이다.
- 완전 탐색: 가능한 경우를 빠짐없이 확인하는 전략
- DFS/BFS: 그래프, 트리, 상태 공간을 어떤 순서로 탐색할지 정하는 방법
따라서 DFS나 BFS를 이용해 모든 가능한 상태를 방문하면 그것도 완전 탐색이다.
경우의 수가 너무 많다면:
- 백트래킹
- 가지치기
등을 사용해 불필요한 탐색을 줄일 수 있다.
