[백준] - 1520 : 내리막 길 (node.js)

문제링크

풀이

처음에는 1890 점프 문제처럼, 각 칸에서 갈 수 있는 방향으로 경우의 수를 누적하는 방식으로 풀었다. 하지만 이 방법은 해당 칸까지 가는 경우의 수가 확정되어 있지 않아 올바른 답이 나오지 않았다.

그러다 위상 순회(Topological Order)라는 접근을 찾았다.
문제의 조건상 항상 더 낮은 높이로만 이동하므로 한 번 갔던 칸을 다시 돌아오는 일이 없다. 즉, 이는 사이클이 없는 DAG(Directed Acyclic Graph) 구조가 된다.

위상순회란 ⭐⭐

그래프에서 순서가 있는 방향대로 노드를 하나씩 처리해 나가는 방법
(이 문제에서는 ‘높이가 높은 칸 → 낮은 칸’ 순서가 해당 방향이다)

풀이 방식은 다음과 같다.

1. 모든 칸을 높이 기준으로 내림차순 정렬한다
2. 가장 높은 칸부터 차례대로 꺼내어, 현재 칸에서 이동 가능한 더 낮은 칸들에게 dp[i][j] 값을 더한다

이렇게 하면 특정 칸에서 이미 그 칸까지 올 수 있는 모든 경로 수가 확정되어 있어 계산이 정확하게 이루어진다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = input[0].split(" ").map(Number);
let l1 = [];
for (let i = 1; i <= n; i++) {
  l1.push(input[i].split(" ").map(Number));
}

let dp = Array.from({ length: n }, () => Array(m).fill(0n));
dp[0][0] = 1n;

let cells = [];
for (let i = 0; i < n; i++) { 
  for (let j = 0; j < m; j++) {
    cells.push([l1[i][j], i, j]);
  }
}
cells.sort((a, b) => b[0] - a[0]); // 내림차순으로 정렬

let dx = [-1, 1, 0, 0];
let dy = [0, 0, -1, 1];
for (const h of cells) {
  let [now, i, j] = h;
  if (i === n - 1 && j == m - 1) continue;
  for (let k = 0; k < 4; k++) {
    let nx = i + dx[k];
    let ny = j + dy[k];
    if (nx < n && ny < m && nx >= 0 && ny >= 0 && l1[nx][ny] < now) {
      dp[nx][ny] += dp[i][j];
    }
  }
}

console.log(dp[n - 1][m - 1].toString());

이외에도 DFS+DP 로도 풀 수 있다. ⭐⭐