같은 격자로 비교하는 DFS와 BFS
네이버 블로그에 작성한 DFS, BFS (2025-05-02)를 바탕으로 설명과 예제를 보완했다.
DFS와 BFS는 방문 순서가 다르다. 스택을 사용하는 DFS는 한 방향을 따라 깊게 탐색하고, 큐를 사용하는 BFS는 시작점에서 가까운 거리부터 탐색한다. 연결된 영역을 찾는 데는 둘 다 쓸 수 있지만, 간선 비용이 같은 그래프의 최단 거리는 BFS로 구할 수 있다.
공통으로 정해야 하는 것
이 예제의 격자는 1이 이동 가능한 칸, 0이 벽이다. 상하좌우 한 칸 이동의 비용은 모두 1이다. 좌표는 (행, 열)이고 시작점은 (0, 0)이다.
1100
0110
0011
시작점도 자료구조에 넣을 때 방문 처리한다. 이웃만 방문 처리하면 시작점이 다른 칸에서 다시 추가될 수 있다. 큐나 스택에 넣는 순간 표시하면 같은 칸을 중복으로 넣는 일을 줄인다.
완전한 C++17 예제
DFS는 큰 입력에서 재귀 호출 스택 한도에 의존하지 않도록 명시적인 스택으로 작성한다. BFS는 방문 여부와 거리를 distance에 함께 저장한다.
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using Grid = std::vector<std::string>;
using Point = std::pair<int, int>;
constexpr int dr[4] = {1, -1, 0, 0};
constexpr int dc[4] = {0, 0, 1, -1};
bool open(const Grid& grid, int r, int c) {
return r >= 0 && r < static_cast<int>(grid.size()) &&
c >= 0 && c < static_cast<int>(grid[0].size()) &&
grid[r][c] == '1';
}
int reachable(const Grid& grid) {
if (grid.empty() || grid[0].empty() || !open(grid, 0, 0)) return 0;
std::vector<std::vector<bool>> visited(
grid.size(), std::vector<bool>(grid[0].size(), false));
std::stack<Point> pending;
pending.push({0, 0});
visited[0][0] = true;
int count = 0;
while (!pending.empty()) {
auto [r, c] = pending.top();
pending.pop();
++count;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (open(grid, nr, nc) && !visited[nr][nc]) {
visited[nr][nc] = true;
pending.push({nr, nc});
}
}
}
return count;
}
int shortest_distance(const Grid& grid) {
if (grid.empty() || grid[0].empty() || !open(grid, 0, 0)) return -1;
std::vector<std::vector<int>> distance(
grid.size(), std::vector<int>(grid[0].size(), -1));
std::queue<Point> pending;
pending.push({0, 0});
distance[0][0] = 0;
while (!pending.empty()) {
auto [r, c] = pending.front();
pending.pop();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (open(grid, nr, nc) && distance[nr][nc] == -1) {
distance[nr][nc] = distance[r][c] + 1;
pending.push({nr, nc});
}
}
}
return distance.back().back();
}
int main() {
const Grid grid{"1100", "0110", "0011"};
std::cout << "reachable=" << reachable(grid) << '\n';
std::cout << "distance=" << shortest_distance(grid) << '\n';
}
c++ -std=c++17 -Wall -Wextra -pedantic traversal.cpp -o traversal
./traversal
reachable=6
distance=5
거리 5는 방문한 칸 수가 아니라 이동 횟수다. 시작점부터 도착점까지 칸 수를 요구하는 문제라면 답의 정의를 맞춰야 한다. 코드는 행 길이가 같은 직사각형 격자를 전제로 하며, 시작점이 막혔거나 목적지에 도달하지 못하면 BFS는 -1을 반환한다.
BFS가 첫 방문 거리를 확정할 수 있는 이유
큐에는 거리 k인 칸들이 거리 k+1인 칸들보다 먼저 처리되도록 들어간다. 따라서 모든 간선 비용이 같으면 어떤 칸을 처음 발견했을 때의 거리가 최단 거리다. 간선마다 가중치가 다르면 이 전제를 사용할 수 없다. 가중치에 맞춰 0-1 BFS나 Dijkstra 등 다른 알고리즘을 검토한다.
DFS는 도달 여부와 영역 크기 계산에 적합하지만 처음 찾은 경로가 최단이라는 보장은 없다. 또한 전역 visited를 두는 이 예제는 도달성을 확인하는 탐색이지 모든 단순 경로를 열거하는 백트래킹 구현이 아니다.
R×C 격자에서 각 칸과 네 방향 이웃을 제한된 횟수만 검사하므로 시간·추가 공간은 O(RC)다. 일반적인 인접 리스트 그래프에서는 탐색 시간이 O(V+E)다.