그리드에서 경로를 하나만 남기기 위해 차단해야 할 셀의 수를 찾는 C++ 프로그램

문제 소개

h × w 크기의 격자(grid)가 있다고 가정해 보겠습니다. 격자의 시작점인 (0, 0) 위치에 로봇이 있으며, 이 로봇은 목적지인 (h − 1, w − 1) 위치로 이동해야 합니다.

격자를 이루는 칸은 막힌 칸(#)과 열린 칸(.) 두 가지입니다. 로봇은 열린 칸은 자유롭게 통과할 수 있지만 막힌 칸은 지나갈 수 없으며, 상·하·좌·우 네 방향으로 움직일 수 있습니다.

그런데 로봇은 한 칸에서 다른 칸으로 이동할 때 직전에 있던 칸을 제외한 어느 방향으로든 움직일 수 있기 때문에, 경로가 여러 갈래로 갈라질 수 있습니다. 따라서 우리는 단 하나의 경로만 남기고, 그 경로에 포함되지 않은 나머지 열린 칸은 모두 차단해야 합니다. 즉, (0, 0)에서 (h − 1, w − 1)까지 이어지는 경로를 정확히 하나 만들기 위해 차단해야 할 칸의 개수를 구해 반환하면 되고, 애초에 경로가 존재하지 않는다면 −1을 반환하면 됩니다.

예를 들어 입력이 h = 4, w = 4, grid = {"..#.", "#.#.", "#.##", "#..."}라면 출력은 2가 됩니다.

그리드에서 경로를 하나만 남기기 위해 차단해야 할 셀의 수를 찾는 C++ 프로그램

그림에서 볼 수 있듯이, (0, 0)에서 (3, 3)까지 이어지는 단일 경로를 만들기 위해서는 단 두 개의 칸만 차단하면 됩니다.

해결 접근 방식

이 문제는 너비 우선 탐색(BFS)을 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

BFS를 통해 (0, 0)에서 (h − 1, w − 1)까지의 최단 경로 길이를 구합니다. 최단 경로 하나만 남기고 나머지 열린 칸을 모두 막으면, 로봇은 그 경로 외에 다른 선택지가 없으므로 조건을 만족합니다.
도착점에 도달할 수 없다면 −1을 반환합니다.
격자 전체의 열린 칸 개수에서 최단 경로에 포함된 칸 개수(최단 거리 + 1)를 빼면, 차단해야 할 칸의 수가 됩니다.

알고리즘 단계

2차원 배열 dp를 선언하고 모든 값을 충분히 큰 값(여기서는 2500, 사실상 무한대 역할)으로 초기화한 뒤, dp[0][0] := 0으로 설정합니다.
네 방향 이동 정보 {{−1, 0}, {1, 0}, {0, −1}, {0, 1}}을 담은 배열 moves를 정의합니다.
큐 q를 만들고 시작 좌표 (0, 0)을 삽입합니다.
큐가 빌 때까지 다음 과정을 반복합니다.
  • 큐의 맨 앞 원소 p를 꺼냅니다.
  • 네 방향 각각에 대해 새 좌표 (row, col)를 계산합니다.
  • 좌표가 격자 범위를 벗어나면 건너뜁니다.
  • 해당 칸이 '#'이면 건너뜁니다.
  • dp[p] + 1이 dp[row][col]보다 작으면 값을 갱신하고 (row, col)을 큐에 삽입합니다.
탐색이 끝난 후 dp[h − 1][w − 1]이 여전히 2500이라면 경로가 없다는 뜻이므로 −1을 반환합니다.
격자 전체를 순회하며 '.'인 칸의 개수를 count에 저장합니다.
count − (dp[h − 1][w − 1] + 1)을 반환합니다. 이 값이 곧 차단해야 할 칸의 수입니다.

이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(h × w)로, 격자 크기에 비례하여 효율적으로 동작합니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다 −

#include <bits/stdc++.h>
using namespace std;

int solve(int h, int w, vector<string> grid){
    vector<vector<int>> dp(h, vector<int>(w, 2500));
    dp[0][0] = 0;
    vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int row = p.first + moves[i].first;
            int col = p.second + moves[i].second;
            if (row < 0 || row > h - 1 || col < 0 || col > w - 1)
                continue;
            if (grid[row][col] == '#')
                continue;
            if (dp[p.first][p.second] + 1 < dp[row][col]) {
                dp[row][col] = dp[p.first][p.second] + 1;
                q.push(make_pair(row, col));
            }
        }
    }
    if (dp[h - 1][w - 1] == 2500) {
        return -1;
    }
    int count = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == '.')
                count++;
        }
    }
    return count - (dp[h - 1][w - 1] + 1);
}

int main() {
    int h = 4, w = 4;
    vector<string> grid = {"..#.", "#.#.", "#.##", "#..."};
    cout<< solve(h, w, grid);
    return 0;
}

입력

4, 4, {"..#.", "#.#.", "#.##", "#..."}