[백준] 1520_내리막 길 (Javascript)

문제

BOJ1520_내리막 길

코드 (시간 초과)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [M, N] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
let answer = 0;
dfs(0, 0);
console.log(answer);

function dfs(x, y) {
    if (x === N - 1 && y === M - 1) {
        answer++;
        return;
    }
    if (x - 1 >= 0 && arr[y][x - 1] < arr[y][x]) dfs(x - 1, y);
    if (x + 1 < N && arr[y][x + 1] < arr[y][x]) dfs(x + 1, y);
    if (y - 1 >= 0 && arr[y - 1][x] < arr[y][x]) dfs(x, y - 1);
    if (y + 1 < M && arr[y + 1][x] < arr[y][x]) dfs(x, y + 1);
}

원인

처음엔 골드3 문제치곤 너무 쉽다고 생각하고 DFS로 풀었는데 시간 시간 초과가 떴다.

생각해보니 사각형의 크기는 500*500이고, 각 칸마다 4방향을 확인하므로 그냥 DFS로 수행하면 최악의 경우 시간복잡도는 O(4^250,000) 이므로 시간초과가 날 수 밖에 없다.

코드 (맞았습니다)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [M, N] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const dp = Array.from({ length: M }, () => Array(N).fill(-1));
console.log(dfs(0, 0));

function dfs(x, y) {
    // 도착 지점에 도달했을 경우 1(한 가지 경우의 수)리턴
    if (x === N - 1 && y === M - 1) return 1;

    // 현재 지점이 이미 방문한적 있는 경우 그 위치에서 출발했을 때의 경우의 수 리턴
    if (dp[y][x] !== -1) return dp[y][x];

    let ways = 0;
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < M && arr[ny][nx] < arr[y][x]) {
            ways += dfs(nx, ny);
        }
    }

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

풀이

이 문제는 DP와 DFS를 같이 사용해야 시간 초과 없이 풀 수 있다.

DP를 사용하면 이미 방문했던 칸에 다시 방문했을 때 해당 위치의 DP테이블을 참조해서 경로의 수를 구할 수 있기 때문에 이미 방문했던 칸을 또다시 방문하지 않아도 되므로 시간이 단축된다.

DP테이블을 0이 아니라 -1로 초기화 하는 이유:
경로를 탐색하던 도중 목적지까지 도달하지 못하고 길이 끊겨 있을 경우 돌아올때 dp[y][x] = ways에 의해 dp[y][x] = 0으로 바뀐다.
dp테이블을 -1로 초기화 했다면 0과 -1이 구분되어 dp[y][x] === 0 인 곳은 if (dp[y][x] !== -1) return dp[y][x]; 에 의해 처리되기 때문에 의도한대로 동작하지만, 만약 dp테이블을 0으로 초기화 했다면, 종료 조건도 if (dp[y][x] !== 0) return dp[y][x]; 이렇게 바뀔 것이고, 아직 한번도 방문하지 않았다는 의미의 0과, 방문한 적은 있지만 목적지까지 가는 경로가 없다는 의미의 0을 구분할 수 없기 때문에 이미 방문한 위치도 다시 방문하여 시간 초과가 난다.

따라서 DP테이블을 0이 아닌 수인 -1로 초기화한 것이다.

참고

https://studyandwrite.tistory.com/387