문제
(0,0)에서 (N,M)까지 오른쪽 또는 위로만 이동할 때, 공사 중인 도로 K개를 피한 최단 경로의 수를 구하라.
입력
첫째 줄에 N, M, 둘째 줄에 공사 중인 도로 수 K, 이후 K줄에 각 도로의 양 끝점 좌표가 주어진다.
출력
(0,0)에서 (N,M)까지의 최단 경로 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 2 0 | 6 |
풀이
2차원 DP로 (0,0)에서 (N,M)까지의 경로 수를 구하되, 공사 중인 도로는 수평/수직 차단 배열로 관리하여 경로에서 제외한다.
- 공사 중인 도로를 수평(horizontal)과 수직(vertical) 차단 배열에 기록한다
- 첫 행과 첫 열의 경로 수를 초기화하되, 차단된 도로가 나오면 이후는 0으로 둔다
dp[i][j] = dp[i-1][j] + dp[i][j-1]에서 차단된 도로에 해당하는 값을 빼서 제외한다- BigInt를 사용하여 큰 수를 처리한다
핵심 아이디어: 기본 격자 경로 DP에서 차단 도로만 빼면 되므로, 추가 배열로 차단 여부를 O(1)에 확인한다.
코드
const solution = (input) => {
const [N, M] = input[0].split(" ").map(Number);
const K = +input[1];
const dp = Array.from(Array(N + 1), () => Array(M + 1).fill(BigInt(0)));
const horizontal = Array.from(Array(N), () => Array(M + 1).fill(0));
const vertical = Array.from(Array(N + 1), () => Array(M).fill(0));
for (let i = 2; i < 2 + K; i++) {
const [x1, y1, x2, y2] = input[i].split(" ").map(Number);
if (y1 === y2) horizontal[Math.min(x1, x2)][y1] = 1; else vertical[x1][Math.min(y1, y2)] = 1;
}
for (let i = 1; i <= N; i++) { if (horizontal[i - 1][0] === 1) break; dp[i][0] = BigInt(1); }
for (let i = 1; i <= M; i++) { if (vertical[0][i - 1] === 1) break; dp[0][i] = BigInt(1); }
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= M; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
if (horizontal[i - 1][j] === 1) dp[i][j] -= dp[i - 1][j];
if (vertical[i][j - 1] === 1) dp[i][j] -= dp[i][j - 1];
}
}
return dp[N][M].toString();
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));복잡도
- 시간: O(N x M)
- 공간: O(N x M)