카테고리 없음
(알고리즘) DFS vs BFS (그래프 탐색 기법 정리)
불광동 물주먹
2025. 5. 3. 16:54
DFS vs BFS (그래프 탐색 기법 정리)
1. 그래프 탐색이란?
그래프 탐색(Graph Traversal)이란, 어떤 노드(정점, Vertex)에서 시작해서 연결된 모든 노드를 빠짐없이 방문하는 과정이다.
그래프는 다음 두 요소로 구성된다:
- Vertex (정점): 탐색의 대상이 되는 지점 (예: 사람, 도시, 방 등)
- Edge (간선): 정점 간의 연결 (예: 친구 관계, 도로, 벽 없는 통로 등)
그래프는 연결되어 있는 방식에 따라 다양한 문제(미로 탐색, 단지 번호 붙이기, 친구 관계 등)에 응용될 수 있다.
2. 탐색 기법 종류
✅ DFS (Depth-First Search, 깊이 우선 탐색)
- 한 방향으로 쭉 들어가며 끝까지 탐색한 뒤, 다시 돌아와서 다른 방향 탐색
- 자식의 자식까지 내려감, 더 이상 갈 곳이 없을 때 되돌아오는 방식
- 주로 재귀 함수 또는 스택으로 구현
- 백트래킹, 조합, 순열, 영역 탐색 등에 사용됨
동작 순서:
1. 현재 노드를 방문처리
2. 인접한 노드 중 방문하지 않은 노드로 이동 (재귀적으로)
3. 갈 곳이 없으면 이전 단계로 돌아감 (Backtracking)
구현 도구:
- 재귀 함수
- 또는 명시적인 스택 자료구조
✅ BFS (Breadth-First Search, 너비 우선 탐색)
- 시작 노드에서 가까운 정점부터 넓게 퍼지듯이 탐색
- 형제 노드(같은 깊이의 노드)를 먼저 모두 방문하고, 다음 깊이로 진행
- 최단 거리 탐색, 계층 구조 순회, 단계별 접근 등에 사용됨
동작 순서:
1. 시작 노드를 방문 처리 후 큐에 삽입
2. 큐에서 노드를 꺼내며 인접한 노드 중 방문하지 않은 노드를 큐에 삽입
3. 큐가 빌 때까지 반복
구현 도구:
- 큐(Queue)
3. DFS / BFS 비교
항목 | DFS | BFS |
기본 전략 | 깊이 우선 | 너비 우선 |
자료구조 | 스택 (또는 재귀) | 큐 |
구현 방식 | 보통 재귀 사용 | 반복문 + 큐 |
방문 순서 | 깊이 → 형제 | 형제 → 깊이 |
용도 | 경로 탐색, 백트래킹 | 최단 거리, 단계별 확산 |
성능 | 깊은 분기 탐색에 유리 | 넓은 범위 탐색에 유리 |
시간 복잡도 | O(V + E) | O(V + E) |
※ V: 정점 수, E: 간선 수
4. DFS 구현 예시 (JAVA)
public class DFSExample {
static int[][] graph;
static boolean[][] visited;
static int n;
// 상하좌우
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (!visited[nx][ny] && graph[nx][ny] == 1) {
dfs(nx, ny);
}
}
}
}
}
5. BFS 구현 예시 (JAVA)
import java.util.LinkedList;
import java.util.Queue;
public class BFSExample {
static int[][] graph;
static boolean[][] visited;
static int n;
// 상하좌우
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
visited[x][y] = true;
while (!queue.isEmpty()) {
int[] pos = queue.poll();
int curX = pos[0];
int curY = pos[1];
for (int i = 0; i < 4; i++) {
int nx = curX + dx[i];
int ny = curY + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (!visited[nx][ny] && graph[nx][ny] == 1) {
visited[nx][ny] = true;
queue.add(new int[]{nx, ny});
}
}
}
}
}
}
6. DFS vs BFS 선택 기준
상황 | 추천 탐색 방식 |
모든 경우의 수 탐색 | DFS (백트래킹) |
경로의 최단 거리 탐색 | BFS |
조합, 순열 문제 | DFS |
가까운 노드 우선 처리 | BFS |
미로처럼 복잡한 구조 탐색 | DFS or BFS 모두 가능 (조건에 따라 선택) |
7. 방문 여부 체크 방법
그래프에서 중복 방문을 막기 위해 방문 여부 기록이 필수이다.
방법은 다음과 같다:
- 2차원 배열 탐색: visited = [[False]*n for _ in range(n)] 또는 입력 배열 자체에 표시 (graph[x][y] = 0)
- 일반 그래프 탐색: visited = [False] * (정점 수 + 1)
마무리 요약
- DFS는 한 방향으로 깊이 파고들며 재귀적으로 탐색
- BFS는 가까운 노드부터 넓게 순차적으로 탐색
- 문제의 성격(최단 거리, 모든 경우의 수 등)에 따라 적절히 선택해야 한다
- DFS는 스택, BFS는 큐 기반의 흐름을 따른다