10. DFS는 바로 들어가고 BFS는 차례를 기다린다
해설글
작성 · 6분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
출발점에서 갈 수 있는 정점을 찾는 문제
입력은 그래프와 출발 정점 하나다. 원하는 답은 출발점에서 간선을 따라 도달할 수 있는 정점을 빠짐없이 한 번씩 처리하는 것이다.
간선: 0-1, 0-2, 1-3, 2-3
출발: 0
가능한 DFS 순서: 0, 1, 3, 2
가능한 BFS 순서: 0, 1, 2, 3
경로(path)는 간선을 이어서 이동한 정점의 순서다. 0→1→3은 간선 두 개를 사용한 경로다. 두 정점 사이에 경로가 있으면 서로 연결되어 있다고 말한다. 무방향 그래프에서 서로 연결된 정점의 최대 묶음을 연결요소라고 한다.
DFS와 BFS는 모두 이웃을 따라가지만 다음에 처리할 작업을 보관하는 곳이 다르다.
| 알고리즘 | 아직 처리하지 않은 작업 | 다음 작업을 꺼내는 기준 |
|---|---|---|
| DFS | 재귀 호출 스택 또는 직접 만든 스택 | 가장 나중에 들어온 탐색 작업을 먼저 처리 |
| BFS | 큐 | 가장 먼저 들어온 정점을 먼저 처리 |
재귀 DFS의 호출 스택은 정점 번호만 쌓아 둔 목록보다 많은 정보를 보존한다. 현재 어느 정점을 처리 중인지, 호출이 끝나면 어느 위치로 돌아갈지, 그 정점에서 다음에 확인할 이웃이 무엇인지가 호출마다 함께 남는다. 직접 스택을 구현할 때도 같은 순서를 재현하려면 정점만 넣을지, 남은 이웃 검사 상태까지 넣을지 구현 방식을 먼저 정해야 한다.
여기서 발견(discovered)은 처음 보고 작업 목록에 넣은 순간이고, 처리(processed)는 그 정점의 이웃을 실제로 훑은 순간이다. BFS에서 이 둘을 구분하지 않으면 같은 정점이 큐에 여러 번 들어갈 수 있다. 아래 개인 기록의 “바로 처리”와 “차례가 밀린다”는 바로 이 작업 상태 차이를 가리킨다.
큐에서 차례가 밀린다는 설명
그래프 순회 노트에는 개념 목록 뒤에 내 말로 길게 풀어 쓴 문장이 남아 있다.
DFS에서는 재귀적으로 바로 처리하는데 BFS에서는 큐에 넣고 큐에서 나오는 과정에서 그 간선 노드의 반대편 정점의 간선 노드들을 큐에 inqueue하는거야.(재귀랑 엇비슷) 그러면 처리 순서가 맨 뒤로 가게 되고 기존에 추가되었던 간선들 먼저 처리가 되는거지!
바로 앞에는 “이해가 드디어 됐어!”라고 적었다. 이 기록에서 이해가 바뀐 지점은 DFS는 스택, BFS는 큐라는 대응표보다 구체적이다. 다음 정점을 지금 처리하느냐, 뒤에 넣어 두고 기존 작업을 먼저 처리하느냐를 구분했다.
다만 같은 노트의 “BFS에서는 재귀적으로”라는 표현은 정리할 필요가 있다. 여기서 구현할 BFS는 재귀 호출 없이 큐와 반복문으로 동작한다. 서로 닮은 것은 이웃의 이웃으로 탐색이 이어진다는 점이고, 실제 호출 방식과 처리 순서는 다르다. 이번에는 노트의 설명을 C 코드로 다시 구성해 그 차이를 따라갔다.
같은 그래프에서 다음 작업을 고른다
이웃을 번호 오름차순으로 살피는 무방향 그래프를 사용하자.
0의 이웃: 1, 2
1의 이웃: 0, 3
2의 이웃: 0, 3
3의 이웃: 1, 2
4의 이웃: 없음
DFS가 0에서 1을 만나면 0의 나머지 이웃인 2를 잠시 남겨 두고 dfs(1)로 들어간다. 1에서 3, 3에서 2로 들어간 뒤 더 갈 곳이 없으면 호출을 거꾸로 빠져나온다. 방문 순서는 0 1 3 2다.
static void dfs_visit(const Graph *g, int u, bool visited[N], int order[N], int *count) {
visited[u] = true; order[(*count)++] = u;
for (Node *p = g->adj[u]; p; p = p->next)
if (!visited[p->vertex]) dfs_visit(g, p->vertex, visited, order, count);
}
p = p->next는 같은 정점의 다른 이웃으로 이동한다. 반면 재귀 호출은 adj[p->vertex]의 이웃들을 살펴보러 들어간다. 재귀에서 돌아왔을 때 이전 호출의 p가 남아 있으므로 보류한 이웃 검사를 이어 갈 수 있다.
여기서는 정점의 방문 여부를 표시한다. 원문에 “간선 방문시 1”이라고 적은 대목이 있지만, 정점을 한 번씩 탐색하려는 이 구현에서 배열 인덱스는 간선이 아니라 정점 번호다.
BFS는 발견했을 때 자리를 예약한다
BFS는 0의 이웃 1과 2를 모두 큐 뒤에 넣는다. 그다음 1을 처리하면서 3을 발견해도, 3은 이미 기다리고 있는 2보다 뒤에 들어간다.
| 방금 처리한 정점 | 처리 뒤 대기 중인 큐 | 새로 발견한 정점 |
|---|---|---|
| 0 | 1, 2 | 1, 2 |
| 1 | 2, 3 | 3 |
| 2 | 3 | 없음 |
| 3 | 비어 있음 | 없음 |
그래서 순서는 0 1 2 3이다. 2를 처리할 때도 이웃 3이 보이지만 다시 큐에 넣지 않는다. 꺼낼 때가 아니라 넣을 때 이미 발견했다고 표시했기 때문이다.
static int bfs(const Graph *g, int start, int order[N], int dist[N], int parent[N]) {
int queue[N], head = 0, tail = 0;
for (int v = 0; v < g->n; ++v) { dist[v] = -1; parent[v] = -1; }
dist[start] = 0; queue[tail++] = start;
while (head < tail) {
int u = queue[head]; order[head++] = u;
for (Node *p = g->adj[u]; p; p = p->next) {
int v = p->vertex;
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1; parent[v] = u;
queue[tail++] = v;
}
}
return tail;
}
dist[v] == -1은 아직 발견하지 않았다는 뜻이다. 큐에 넣기 직전에 거리를 기록하므로 정점 하나가 여러 부모 후보에게 중복 예약되지 않는다. 정점이 V개면 큐에 들어가는 횟수도 최대 V회라 이 예시의 고정 배열 큐로 충분하다. N=16은 검증 프로그램의 입력 한도이며, 실제 입력을 받는 프로그램에서는 그 크기를 맞춰 할당해야 한다.
거리가 함께 나오는 이유
큐에는 출발점에서 간선 하나로 닿는 정점들이 먼저 쌓이고, 그다음 두 개, 세 개로 닿는 정점들이 쌓인다. u를 처리하며 v를 처음 발견했다면 dist[v] = dist[u] + 1이다. 더 적은 간선으로 v에 도착할 수 있었다면 더 앞 단계에서 이미 발견했어야 한다.
이번 실행은 다음과 같았다.
DFS: 0 1 3 2
BFS: 0 1 2 3
BFS distances: 0 1 1 2 -1
여기서 거리는 간선 개수다. 가중치가 제각각인 그래프의 요금이나 시간을 최소화한 값이 아니다. 0→2가 100원이고 0→1→3→2가 총 3원이어도 BFS는 한 간선짜리 경로를 먼저 발견한다. 가중치가 같은 경우에만 간선 수 최소화와 비용 최소화가 일치한다. Algorithms, 4th Edition의 BFS와 최단 경로 설명
parent[v]는 처음 발견한 간선의 출발 정점을 기록한다. 위 실행에서 3의 부모는 1이므로 3→1→0을 거꾸로 따라가 경로를 복원할 수 있다. 이웃 순서를 바꾸면 최단 경로 후보 중 다른 부모를 고를 수 있지만 최소 간선 수는 같다.
한 번의 시작으로 모두 방문되지는 않는다
고립 정점 4의 거리는 -1로 남는다. 0에서 출발한 순회는 0과 연결된 부분만 방문한다. 전체 그래프를 빠짐없이 훑으려면 아직 방문하지 않은 정점마다 순회를 다시 시작해야 한다. 무방향 그래프에서는 그 횟수로 연결요소 수도 셀 수 있다.
인접리스트를 사용하는 전체 순회는 O(V+E) 시간이다. DFS는 깊이가 V에 가까워지면 호출 스택도 O(V)까지 늘고, BFS 역시 큐와 거리 배열에 O(V) 공간을 사용한다. 긴 사슬 입력에서는 재귀 호출 한도를 따로 고려해야 한다.
새 검증에서는 정점 4개의 자기 루프 없는 모든 방향 그래프 4,096개를 만들었다. 각 시작점에서 BFS 거리를 별도의 행렬 기반 최단 거리 계산과 비교하고, DFS가 방문한 집합도 같은 도달 가능성과 대조했다. 특정 방문 순서 하나를 외우는 대신, 무엇을 방문해야 하고 거리가 무엇이어야 하는지를 확인한 셈이다.
노트의 “기존에 추가되었던 간선들 먼저”라는 말은 이제 “먼저 발견해서 큐에 넣어 둔 정점부터 처리한다”로 고쳐 적을 수 있다. 내가 붙잡았던 처리 순서의 감각을 유지하면서, 무엇을 저장하고 표시하는지까지 분명히 하는 정리다.
기록과 실행 코드
- 개인 노트 「11주차-그래프 순회」, 2025-12-15
- 이번에 작성한 C 코드와 검증 전체:
dfs_visit,bfs,check_directed