백준 1520 JS 풀이 (시간초과)

구하는 값

낮은 높이로만 이동해서 목표지점 도달하는 경우의 수

핵심 아이디어

DFS로만 풀면 시간초과가 생긴다. 다른사람들 풀이를 보니 DP로 메모이제이션을 해줘야 한다고 한다.

DP학습 후에 다시 풀어봐야겠다.

코드

const input = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");

const [m, n] = input[0].split(" ").map(Number);
const graph = [];
for (let i = 1; i <= m; i++) graph.push(input[i].split(" ").map(Number));
// console.log(graph);
const visited = Array.from({ length: m }, () => new Array(n).fill(false));
const dx = [-1, 1, 0, 0],
    dy = [0, 0, -1, 1];

const init = graph[0][0];
graph.forEach((line, i) => {
    line.forEach((v, j) => {
        if (v >= init) visited[i][j] = true;
    });
});

let cnt = 0;
const dfs = (y, x, prev) => {
    if (y === m - 1 && x === n - 1) {
        cnt++;
        return;
    }

    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i],
            ny = y + dy[i];

        if (ny < 0 || ny >= m || nx < 0 || nx >= n) continue;
        const cur = graph[ny][nx];
        if (!visited[ny][nx] && cur < prev) {
            visited[ny][nx] = true;
            dfs(ny, nx, cur);
            visited[ny][nx] = false;
        }
    }
    return;
};

visited[0][0] = true;
dfs(0, 0, init);

console.log(cnt);