ReadizBFS/DFS와 격자 탐색: 발견과 방문의 순서
큐와 스택으로 상태를 탐색하고, 같은 비용의 이동에서 최단거리를 구합니다.
이 글의 목차
미로에서 갈 수 있는 칸을 찾는 일과 가장 짧은 길을 찾는 일은 비슷해 보여도 방문 순서의 역할이 다릅니다. 이 강의는 발견 표시 → 큐의 거리 순서 → 격자 경계 → 상태 확장의 순서로 이어집니다. 배열과 반복문을 알면 시작할 수 있습니다.
BFS와 DFS는 그래프에서 갈 수 있는 곳을 빠짐없이 방문하는 가장 기본적인 탐색 방법입니다. 문제에서 정점과 간선이 직접 나오지 않아도, 격자 칸, 지도, 상태 전이, 이동 가능한 위치를 그래프로 보면 같은 도구를 쓸 수 있습니다.
DFS: 한 방향으로 깊게 들어갔다가 돌아온다.
BFS: 시작점에서 가까운 곳부터 차례로 본다.아래 예시는 미방문 정점 표시와 최단거리 계산의 차이를 다룹니다. 인접 목록 표현은 그래프와 트리에 있습니다.
그래프로 생각하기
격자에서는 보통 한 칸이 정점이고, 상하좌우로 이동할 수 있으면 간선이 있다고 봅니다.
....
.##.
..... 칸은 지나갈 수 있고, # 칸은 벽이라면 각 . 칸이 정점입니다. 상하좌우로 붙어 있는 . 칸 사이에 간선이 있습니다.
발견한 시점에 방문 표시하기
합류하는 정점이 있는 예제에서 큐에 넣는 순간 거리가 정해지는지 확인해 보세요. 이미 발견한 정점에 다시 도달해도 큐에 중복으로 넣지 않습니다.
아래 방향 그래프에서 A와 B는 모두 C를 발견할 수 있습니다. 큐에 넣을 때 C의 거리를 기록하면 C는 한 번만 들어가고, S에서의 거리 2가 확정됩니다.
이미 발견한 정점을 다시 넣지 않도록 표시합니다. BFS나 반복 DFS에서는 큐·스택에서 꺼낼 때까지 기다리지 않고 넣는 순간 표시해야 여러 이웃이 같은 정점을 중복으로 넣지 않습니다.
S의 거리 0에서 A·B의 거리 1을 발견하고, A에서 C의 거리 2를 기록합니다. 아직 C를 꺼내지 않았어도 이미 발견된 상태입니다. B에서 C로 가는 간선을 볼 때는 다시 넣지 않습니다. 꺼낼 때까지 표시를 미루면 큐 안에 같은 정점이 여러 번 들어갈 수 있습니다.
DFS도 갈 수 있는 정점을 찾지만 처음 발견한 경로의 길이가 최단거리라는 보장은 없습니다. 예를 들어 S→A→B→G와 S→G가 함께 있을 때, DFS는 이웃을 보는 순서에 따라 길이 3의 경로를 먼저 찾습니다. BFS는 한 번 이동한 정점부터 처리하므로 길이 1을 찾습니다.
DFS
한 경로를 따라 깊이 들어갔다가 되돌아옵니다. 아래 함수는 u와 연결된 모든 정점을 표시합니다.
코드 환경: 일반 C++17 학습용. 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.
void dfs(int u, const vector<vector<int>>& graph, vector<int>& visited) {
visited[u] = 1;
for (int v : graph[u]) {
if (visited[v]) continue;
dfs(v, graph, visited);
}
}길게 이어진 그래프에서는 재귀 깊이도 정점 수만큼 늘어납니다. 실행 환경의 스택 제한을 넘는다면 명시적인 스택으로 바꿉니다. 다음 구현은 방문한 정점 수도 반환합니다.
int dfsSizeIterative(int start, const vector<vector<int>>& graph, vector<int>& visited) {
int size = 0;
vector<int> stack;
visited[start] = 1;
stack.push_back(start);
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
size++;
for (int v : graph[u]) {
if (visited[v]) continue;
visited[v] = 1;
stack.push_back(v);
}
}
return size;
}BFS로 최단거리 구하기
모든 간선 비용이 1이면 거리 0, 1, 2인 정점 순서로 큐에서 나옵니다. dist[v] == -1을 미방문 표시로 함께 사용합니다.
vector<int> shortestDistance(int start, const vector<vector<int>>& graph) {
int n = (int)graph.size();
vector<int> dist(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
return dist;
}새 정점은 현재 거리보다 정확히 1 멀리 있으므로 처음 넣을 때 거리가 확정됩니다. 다른 비용의 간선이 섞이면 이 성질이 깨집니다. 큐의 배열 구현은 공통 코드를 참고합니다.
연결 요소 세기
무방향 그래프에서 연결 요소 개수는 아직 방문하지 않은 정점마다 탐색을 시작해서 셉니다.
int countComponents(const vector<vector<int>>& graph) {
int n = (int)graph.size();
vector<int> visited(n, 0);
int components = 0;
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
components++;
dfs(i, graph, visited);
}
return components;
}격자를 탐색할 때의 경계
격자 칸을 정점으로 보고 상하좌우 이웃을 생성합니다. 다음 좌표를 만든 뒤에는 배열을 읽기 전에 범위를 확인해야 합니다. 범위 안이면 벽인지, 이미 방문했는지 검사합니다. 이 순서를 아래 gridDistance의 내부 반복문에서 확인할 수 있습니다.
격자 BFS 최단거리
상하좌우 이동 비용이 모두 1이면 격자 최단거리는 BFS입니다. 시작점이 유효한 빈 칸이라는 보장이 없다면, 큐에 넣기 전에 범위와 벽 여부를 검사합니다.
vector<vector<int>> gridDistance(
const vector<string>& grid,
int sy,
int sx
) {
int h = (int)grid.size();
int w = h == 0 ? 0 : (int)grid[0].size();
vector<vector<int>> dist(h, vector<int>(w, -1));
queue<pair<int, int>> q;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
if (sy < 0 || sy >= h || sx < 0 || sx >= w || grid[sy][sx] == '#') return dist;
dist[sy][sx] = 0;
q.push({sy, sx});
while (!q.empty()) {
auto [y, x] = q.front();
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
if (grid[ny][nx] == '#') continue;
if (dist[ny][nx] != -1) continue;
dist[ny][nx] = dist[y][x] + 1;
q.push({ny, nx});
}
}
return dist;
}여러 곳에서 동시에 퍼질 때
위 구현에서 시작점 하나를 넣는 부분만 바꿉니다. 모든 유효한 시작점의 거리를 0으로 두고 큐에 넣은 뒤 같은 반복문을 실행합니다. 같은 좌표가 여러 번 주어지면 처음 한 번만 넣습니다.
얻는 거리는 시작점 각각까지의 거리가 아니라 가장 가까운 시작점까지의 거리입니다. 불이 여러 곳에서 동시에 번진다면 각 칸에 최초로 도착하는 시간을 한 번의 탐색으로 구할 수 있습니다.
상태 그래프
격자 칸만 정점이 되는 것은 아닙니다. 방향, 남은 자원, 열쇠 보유 상태까지 포함해야 할 때도 있습니다.
(y, x)만으로는 부족하다.
로봇 방향까지 같아야 같은 상태다.
남은 배터리나 사용한 특수 이동 횟수가 다르면 다른 상태다.이때 정점은 (y, x, dir) 또는 (y, x, used) 같은 상태가 됩니다. 방문 배열도 그 차원만큼 늘어납니다.
상태를 넓히면 정점 수가 크게 늘어납니다. h * w * stateCount가 시간과 메모리 안에 들어오는지 먼저 계산해야 합니다.
BFS와 Dijkstra의 차이
BFS가 최단거리를 보장하는 이유는 모든 간선 비용이 같기 때문입니다. 큐에서 먼저 나오는 상태가 항상 더 짧은 거리입니다.
간선 비용이 서로 다르면 일반 BFS는 틀릴 수 있습니다.
| 간선 비용 | 적합한 알고리즘 |
|---|---|
| 모두 1 | BFS |
| 0 또는 1 | 0-1 BFS |
| 음수 없음, 여러 양수 | Dijkstra |
| 음수 가능 | Bellman-Ford 등 별도 기법 |
격자라도 이동마다 비용이 다르면 BFS가 아니라 Dijkstra를 검토해야 합니다.
시간 복잡도
각 정점과 간선을 한 번씩 보면 됩니다.
인접 리스트 그래프: O(V + E)
격자 상하좌우 탐색: O(HW)
메모리: 방문 배열 또는 거리 배열 O(V)격자에서 각 칸의 이웃은 최대 4개라서 간선 수가 O(HW)입니다. 그래서 격자 BFS/DFS도 전체 칸 수에 비례합니다.
상태 그래프에서는 V가 실제 상태 수입니다.
위치만 상태: H * W
위치 + 방향: H * W * 4
위치 + 열쇠 bitmask: H * W * 2^K상태를 추가할수록 복잡도가 곱으로 늘어납니다.
로컬 연습: 장애물 격자의 최단 이동
상하좌우로 한 칸씩 이동할 때 시작 칸에서 목표 칸까지의 최소 이동 횟수를 구하세요. .은 통로, #은 벽입니다.
입력: H W sy sx ty tx 뒤 H줄의 격자. 1 <= H,W <= 500이고 좌표는 0-based이며 시작·목표는 통로입니다.
출력: 최소 이동 횟수, 도달 불가이면 -1을 출력합니다.
예시
4 5 0 0 3 4
...#.
.#...
.#.#.
...#.7확인 방법: 작은 격자는 모든 통로 사이 거리를 Floyd-Warshall로 구해 비교합니다. 시작=목표이면 0이며 통로가 끊기면 -1입니다. BFS는 큐에 넣을 때 방문 처리해 각 칸을 한 번만 넣고, 큐 용량은 H*W로 둡니다.
완성 파일로 실행하고 확인하기
c++ -std=c++17 -O2 bfs-dfs-grid.cpp -o lesson
./lesson < input.txt위 로컬 연습의 입력을 그대로 읽는 C++17 파일입니다. 본문의 다섯 함수를 포함하며 main은 gridDistance로 목표까지 거리를 출력합니다. 시작과 목표가 같으면 0, 도달할 수 없으면 -1입니다. 본문의 countComponents는 재귀 DFS를 사용하므로 긴 사슬 그래프에서는 dfsSizeIterative를 쓰는 편이 안전합니다.
다중 시작점은 모든 출발점을 거리 0으로 동시에 넣어야 합니다. 예를 들어 일렬 통로 5칸의 양 끝에서 시작하면 거리는 [0,1,2,1,0]입니다. 출발점별로 구한 거리들을 더하는 것이 아니라 각 칸까지의 최솟값을 구합니다.
직접 확인할 입력은 세 가지입니다. 1×1 통로에서 시작=목표이면 0, 1×3의 .#. 양 끝이면 -1, 1×3의 ... 양 끝이면 2입니다. 작은 격자에서는 모든 통로 쌍의 Floyd-Warshall 결과와 비교할 수 있습니다.
Dense BFS 응용 노트도 함께 볼 수 있습니다. 기존 기록의 코드·작성 시점은 유지하며, 이 강의의 다운로드 파일을 현재 실습 기준으로 사용합니다.
이전 사이트에서 옮긴 글입니다. 원래 주소