---
id: "lessons/bfs-dfs-grid"
title: "BFS/DFS와 격자 탐색: 발견과 방문의 순서"
description: "큐와 스택으로 상태를 탐색하고, 같은 비용의 이동에서 최단거리를 구합니다."
kind: "record"
published: "2026-10-04T00:00:00.000Z"
tags: ["알고리즘","C++","그래프"]
url: "https://www.readiz.com/records/bfs-dfs-grid/"
markdownUrl: "https://www.readiz.com/records/bfs-dfs-grid/index.md"
---

# BFS/DFS와 격자 탐색: 발견과 방문의 순서

미로에서 갈 수 있는 칸을 찾는 일과 가장 짧은 길을 찾는 일은 비슷해 보여도 방문 순서의 역할이 다릅니다. 이 강의는 발견 표시 → 큐의 거리 순서 → 격자 경계 → 상태 확장의 순서로 이어집니다. 배열과 반복문을 알면 시작할 수 있습니다.

BFS와 DFS는 그래프에서 갈 수 있는 곳을 빠짐없이 방문하는 가장 기본적인 탐색 방법입니다. 문제에서 정점과 간선이 직접 나오지 않아도, 격자 칸, 지도, 상태 전이, 이동 가능한 위치를 그래프로 보면 같은 도구를 쓸 수 있습니다.

```text
DFS: 한 방향으로 깊게 들어갔다가 돌아온다.
BFS: 시작점에서 가까운 곳부터 차례로 본다.
```

아래 예시는 미방문 정점 표시와 최단거리 계산의 차이를 다룹니다. 인접 목록 표현은 [그래프와 트리](https://h.readiz.com/learn/graph-tree-basics)에 있습니다.

## 그래프로 생각하기

격자에서는 보통 한 칸이 정점이고, 상하좌우로 이동할 수 있으면 간선이 있다고 봅니다.

```text
....
.##.
....
```

`.` 칸은 지나갈 수 있고, `#` 칸은 벽이라면 각 `.` 칸이 정점입니다. 상하좌우로 붙어 있는 `.` 칸 사이에 간선이 있습니다.

## 발견한 시점에 방문 표시하기

[BFS: 발견 표시와 큐를 함께 따라가기](https://www.readiz.com/learn/lab/?demo=bfs)

합류하는 정점이 있는 예제에서 큐에 넣는 순간 거리가 정해지는지 확인해 보세요. 이미 발견한 정점에 다시 도달해도 큐에 중복으로 넣지 않습니다.

아래 방향 그래프에서 A와 B는 모두 C를 발견할 수 있습니다. 큐에 넣을 때 C의 거리를 기록하면 C는 한 번만 들어가고, S에서의 거리 2가 확정됩니다.

이미 발견한 정점을 다시 넣지 않도록 표시합니다. BFS나 반복 DFS에서는 큐·스택에서 꺼낼 때까지 기다리지 않고 **넣는 순간** 표시해야 여러 이웃이 같은 정점을 중복으로 넣지 않습니다.

![S에서 A와 B를 거쳐 C에 합류합니다. A가 C를 처음 발견할 때 거리 2와 방문 표시를 기록하면 B에서는 C를 다시 넣지 않습니다.](https://www.readiz.com/assets/lessons/graph-search/bfs-discovery.svg)

[그림 크게 보기](https://www.readiz.com/assets/lessons/graph-search/bfs-discovery.svg)

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 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
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);
    }
}
```

길게 이어진 그래프에서는 재귀 깊이도 정점 수만큼 늘어납니다. 실행 환경의 스택 제한을 넘는다면 명시적인 스택으로 바꿉니다. 다음 구현은 방문한 정점 수도 반환합니다.

```cpp
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`을 미방문 표시로 함께 사용합니다.

```cpp
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 멀리 있으므로 처음 넣을 때 거리가 확정됩니다. 다른 비용의 간선이 섞이면 이 성질이 깨집니다. 큐의 배열 구현은 [공통 코드](https://h.readiz.com/learn/cpp-common-library)를 참고합니다.

## 연결 요소 세기

무방향 그래프에서 연결 요소 개수는 아직 방문하지 않은 정점마다 탐색을 시작해서 셉니다.

```cpp
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입니다. 시작점이 유효한 빈 칸이라는 보장이 없다면, 큐에 넣기 전에 범위와 벽 여부를 검사합니다.

```cpp
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으로 두고 큐에 넣은 뒤 같은 반복문을 실행합니다. 같은 좌표가 여러 번 주어지면 처음 한 번만 넣습니다.

얻는 거리는 시작점 각각까지의 거리가 아니라 **가장 가까운 시작점까지의 거리**입니다. 불이 여러 곳에서 동시에 번진다면 각 칸에 최초로 도착하는 시간을 한 번의 탐색으로 구할 수 있습니다.

## 상태 그래프

격자 칸만 정점이 되는 것은 아닙니다. 방향, 남은 자원, 열쇠 보유 상태까지 포함해야 할 때도 있습니다.

```text
(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를 검토해야 합니다.

## 시간 복잡도

각 정점과 간선을 한 번씩 보면 됩니다.

```text
인접 리스트 그래프: O(V + E)
격자 상하좌우 탐색: O(HW)
메모리: 방문 배열 또는 거리 배열 O(V)
```

격자에서 각 칸의 이웃은 최대 4개라서 간선 수가 `O(HW)`입니다. 그래서 격자 BFS/DFS도 전체 칸 수에 비례합니다.

상태 그래프에서는 `V`가 실제 상태 수입니다.

```text
위치만 상태: H * W
위치 + 방향: H * W * 4
위치 + 열쇠 bitmask: H * W * 2^K
```

상태를 추가할수록 복잡도가 곱으로 늘어납니다.

## 로컬 연습: 장애물 격자의 최단 이동

상하좌우로 한 칸씩 이동할 때 시작 칸에서 목표 칸까지의 최소 이동 횟수를 구하세요. .은 통로, #은 벽입니다.

**입력:** H W sy sx ty tx 뒤 H줄의 격자. 1 <= H,W <= 500이고 좌표는 0-based이며 시작·목표는 통로입니다.

**출력:** 최소 이동 횟수, 도달 불가이면 -1을 출력합니다.

### 예시

```text exercise=bfs-dfs-grid role=input
4 5 0 0 3 4
...#.
.#...
.#.#.
...#.
```

```text exercise=bfs-dfs-grid role=output
7
```

**확인 방법:** 작은 격자는 모든 통로 사이 거리를 Floyd-Warshall로 구해 비교합니다. 시작=목표이면 0이며 통로가 끊기면 -1입니다. BFS는 큐에 넣을 때 방문 처리해 각 칸을 한 번만 넣고, 큐 용량은 H\*W로 둡니다.

## 완성 파일로 실행하고 확인하기

[C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/graph-search/bfs-dfs-grid.cpp)

```sh
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 응용 노트](https://www.readiz.com/notes/algorithm/graph/dense-bfs/)도 함께 볼 수 있습니다. 기존 기록의 코드·작성 시점은 유지하며, 이 강의의 다운로드 파일을 현재 실습 기준으로 사용합니다.

## 관련 문서

- [Dense BFS](https://www.readiz.com/notes/algorithm/graph/dense-bfs/index.md)