[백준 1520 - Node.js] 내리막길

🔗 문제 링크

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [M, N] = input.shift().split(' ').map(Number);
const map = input.map(v => v.split(' ').map(Number));
const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const dp = [...Array(M)].map(() => Array(N).fill(-1));
dp[M - 1][N - 1] = 1;

const dfs = (x, y) => {
  if (dp[x][y] !== -1) {
    return dp[x][y];
  }
  let count = 0;

  for (let i = 0; i < 4; i++) {
    const nx = x + offset[i][0];
    const ny = y + offset[i][1];
    if (
      nx >= 0 && nx < M && ny >= 0 && ny < N
        && map[x][y] > map[nx][ny]
    ) {
      count += dfs(nx, ny);
    }
  }

  dp[x][y] = count;
  return count;
};

console.log(dfs(0, 0));

이 문제는 단순히 DFS만으로는 시간 초과가 나서 풀 수 없다.

 

처음에는 visited 배열도 만들고, 방문할 때마다 visited를 true로 갱신하고, DFS가 끝나면 다시 false로 갱신하기를 반복하여 가능한 모든 경로를 다 탐색하도록 하였다. 그러나 이러한 방식으로는 중복 탐색이 일어나기 때문에 M과 N의 증가에 따라 경우의 수가 기하급수적으로 증가한다.

 

예를 들어, 시작점이 (0, 0)이고 도착점이 (4, 4)라고 하자.

시작점 (0, 0)에서 (1, 1)까지 가는데 여러 가지 방법이 있을 것이다.

우-하, 하-우로 이동할 수도 있고, 경우에 따라서는 우-우-하-좌, 하-하-우-상 등의 경로도 존재할 수 있을 것이다.

 

시작점에서 (1, 1)을 거쳐서 도착점까지 가는 경우에 시작점인 (0, 0)에서 (1, 1)까지 어떤 경로로 왔든 상관 없이 (1, 1)에서 (4, 4)까지 가는 경우의 수는 동일할 것이다. 단순히 DFS만을 사용하면 (0, 0)에서 (1, 1)까지 도달하는 모든 경로에서 (1, 1) 에서 (4, 4)까지 가는 경우의 수를 계산하는 것을 반복하게 된다.

 

따라서 최초로 (1, 1)을 거쳐 (4, 4)에 도달하는 경로가 나왔다면 그 때의 경우의 수를 기록해뒀다가 이후에 또 다른 경로에서 (1, 1)에 도달했을 때 이 경우의 수를 재활용할 수 있다.

 

위 코드에서는 Top-Down 방식으로 DP배열의 DP[x][y]에 (x, y)에서 도착점까지 가는 경우의 수를 기록하였다. 이렇게 하면 DP[0][0]에 구하고자 하는 경로의 개수가 저장된다.

 

그리고 DP배열이 갱신되었는지 여부, 즉 이미 (x, y)에서 도착점까지 간 적이 있는지 여부를 DFS에서 먼저 확인하여 간 적이 있다면 DP[x][y]의 값을 재활용하고, 간 적이 없을 때에만 4방향에 대한 탐색을 재귀로 진행한다.

이렇게 DP배열의 갱신 여부를 통해 이미 가 본 경로에 대해 4방향 탐색을 하지 않으므로 따로 visited 배열을 만들 필요가 없다.

 

도착점에 대한 DP배열인 dp[M - 1][N - 1]을 1로 초기화한 이유는, 미리 초기화하지 않으면 count 값이 들어가는데, 도착점에서는 4방향 탐색을 하지 않을 것이기 때문에 count의 초기값인 0이 DP배열에 저장된다. 도착을 했는데도 불구하고 경로의 수가 0이 되어 모든 이동 가능한 경로의 DP배열이 0으로 갱신될 것이다.

 

DP배열을 처음에는 0으로 초기화하였는데 시간 초과가 났다. 왜냐하면 (x, y)에서 도착점으로 가는 경로의 수가 0일 수도 있는데, 0을 초기값으로 하면 갱신 여부를 정확히 판단하지 못해서 중복 탐색이 일어나기 때문이다. 그래서 DP배열을 -1로 초기화하는 방식으로 바꾸었더니 통과하였다.