왼쪽 위에서 오른쪽 아래까지 상하좌우로 한 칸씩 이동해요. 0은 열린 칸, 1은 벽이에요. 가능한 최단 이동 경로의 개수를 1,000,000,007로 나눈 나머지를 구해요. 경로는 지나가는 칸의 순서가 다르면 다른 경로예요.
int solution(vector<vector<int>> board)의 잘못된 한 줄을 고쳐 주세요. 행·열은 각각 1~5, 모든 행의 길이는 같으며 값은 0 또는 1이에요. 시작·도착도 벽일 수 있고 이때와 도달 불가능할 때는 0이에요. 열린 1×1은 이동 없는 경로 한 개로 1을 반환해요. 빈 배열은 없고 반환형은 int예요.
예시 1: board = {{0, 0, 0}, {0, 0, 0}} → 3. 최단 3번 이동 중 아래로 이동하는 위치를 세 곳에서 고를 수 있어요.
예시 2: board = {{0, 0, 1}, {0, 1, 0}, {0, 0, 0}} → 1. 왼쪽 가장자리를 내려가 아래쪽으로 가는 경로만 최단이에요. 도착 뒤 위쪽 칸을 방문하고 돌아오는 이동은 최단 경로가 아니에요.
실행 입력은 R C, 다음 R줄의 C 개 값이에요. main은 하네스이며 경로 수의 나머지를 출력해요.
예시 입력
2 3
0 0 0
0 0 0
예상 결과
3
예시 입력
3 3
0 0 1
0 1 0
0 0 0
예상 결과
1
핵심 개념
bfs-grid: 먼저 도착하는 거리와 방문 조건을 유지해요.dp-2d: 좌표와 추가 상태에 따른 의존 관계를 읽어요.stack-queue: 가장 최근 상태와 먼저 들어온 상태를 구분해요.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<vector<int>> board) {
const int MOD = 1000000007;
int rows = (int)board.size(), cols = (int)board[0].size(), n = rows * cols;
if (board[0][0] || board[rows - 1][cols - 1]) return 0;
vector<int> dist(n, -1), ways(n, 0);
queue<int> q;
dist[0] = 0; ways[0] = 1; q.push(0);
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
while (!q.empty()) {
int id = q.front(); q.pop();
int r = id / cols, c = id % cols;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || board[nr][nc]) continue;
int next = nr * cols + nc;
if (dist[next] == -1) {
dist[next] = dist[id] + 1;
ways[next] = ways[id];
q.push(next);
} else if (dist[next] >= 0) {
ways[next] = (ways[next] + ways[id]) % MOD;
}
}
}
return ways[n - 1];
}
int main() {
int rows, cols; cin >> rows >> cols;
vector<vector<int>> board(rows, vector<int>(cols));
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c) cin >> board[r][c];
cout << solution(board) << '\n';
}