C++로 풀어보는 고유 경로 III(Unique Paths III) — DFS 백트래킹 풀이

문제 소개

2차원 격자가 하나 주어져 있고, 각 칸은 다음 네 가지 유형 중 하나입니다.

• 1 : 시작 지점 — 격자 안에 정확히 하나만 존재합니다.
• 2 : 도착 지점 — 역시 정확히 하나만 존재합니다.
• 0 : 자유롭게 걸어 다닐 수 있는 빈 칸입니다.
• -1 : 지나갈 수 없는 장애물입니다.

목표는 시작 지점에서 도착 지점까지, 장애물이 아닌 모든 칸을 정확히 한 번씩만 밟으면서 상하좌우 네 방향으로만 이동하는 경로의 개수를 구하는 것입니다.

예시 입력

이 경우 정답은 2입니다. 가능한 두 경로는 다음과 같습니다.

1. (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (1,2) → (1,1) → (1,0) → (2,0) → (2,1) → (2,2)
2. (0,0) → (1,0) → (2,0) → (2,1) → (1,1) → (0,1) → (0,2) → (0,3) → (1,3) → (1,2) → (2,2)

풀이 접근법 : DFS + 백트래킹

이 문제는 깊이 우선 탐색(DFS)과 백트래킹을 조합하면 깔끔하게 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.

1. 사전 준비 — 격자 전체를 한 번 순회하면서 빈 칸(0)의 개수 empty, 시작 좌표 (sx, sy), 도착 좌표 (ex, ey)를 파악합니다.
2. 시작 좌표에서 dfs()를 호출합니다. 이 함수는 격자, 현재 위치 (i, j), 도착 좌표 (ex, ey), 남은 빈 칸 수 empty를 인자로 받습니다.
3. 현재 위치가 격자 범위를 벗어나거나 해당 칸이 장애물(-1)이면 유효한 경로가 아니므로 0을 반환합니다.
4. 현재 위치가 도착점(2)이라면, empty == -1, 즉 모든 빈 칸을 이미 방문한 경우에만 true(1)를 반환합니다. 중간에 도달했다면 경로로 인정되지 않습니다.
5. 그 외의 경우에는 현재 칸을 임시로 장애물 처리(-1)하고 empty를 1 감소시킨 뒤, 네 방향으로 재귀 호출을 진행합니다.
6. 네 방향 탐색이 끝나면 empty를 되돌리고 현재 칸을 다시 0으로 복원(백트래킹)한 후, 누적된 경로의 수 x를 반환합니다.

핵심은 탐색이 끝난 뒤 격자 상태를 반드시 원상 복구해야 한다는 점입니다. 이렇게 해야 서로 다른 경로들이 같은 격자 상태에서 독립적으로 탐색될 수 있습니다.

C++ 구현 예제

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

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int i, int j, int ex, int ey, int empty){
        if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0 || grid[i][j] == -1)
            return 0;
        if (grid[i][j] == 2) {
            return empty == -1;
        }
        int x = 0;
        empty--;
        grid[i][j] = -1;
        for (int k = 0; k < 4; k++) {
            int nx = i + dir[k][0];
            int ny = j + dir[k][1];
            x += dfs(grid, nx, ny, ex, ey, empty);
        }
        empty++;
        grid[i][j] = 0;
        return x;
    }

    int uniquePathsIII(vector<vector<int>>& grid){
        int empty = 0;
        int sx, sy, ex, ey;
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0)
                    empty++;
                else if (grid[i][j] == 1) {
                    sx = i;
                    sy = j;
                }
                else if (grid[i][j] == 2) {
                    ex = i;
                    ey = j;
                }
            }
        }
        return dfs(grid, sx, sy, ex, ey, empty);
    }
};

main(){
    Solution ob;
    vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
    cout << (ob.uniquePathsIII(v));
}

입력

{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}

출력

2

복잡도 분석 및 마무리

최악의 경우 각 칸마다 최대 네 방향을 시도하므로 시간 복잡도는 지수형(O(4^(N×M)) 상한)이지만, '모든 칸을 한 번씩만 방문'이라는 제약 덕분에 실제 탐색 공간은 훨씬 줄어듭니다. 공간 복잡도는 재귀 호출 스택 깊이에 비례하여 O(N×M)입니다.

이처럼 DFS에 백트래킹을 더해 방문 상태를 관리하는 패턴은 Unique Paths 시리즈는 물론, 미로 탐색·스도쿠·N-Queens 같은 다양한 그리드 기반 문제에도 그대로 응용할 수 있으니 꼭 익혀 두시길 바랍니다.