[JavaScript/DFS/DP] 백준 골드 3 : 1937 - 욕심쟁이 판다

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

---

📌 작성한 코드 

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

const N = Number(input.shift());
const board = input.map((str) => str.split(" ").map(Number));

// 먹고 상하좌우로 이동 / 옮긴 지역에 전 지역보다 대나무가 많이 있어야 함
// 최대한 많은 칸을 이동하려면 어떤 경로를 통해야 하는지

// dp[i][j] = i,j에서 시작해서 이동 가능한 최대값
// dp를 계속 사용해도 되는 이유 : 대나무가 많아지는 순서대로 이동해야 하기때문에 어차피 이전에 먹었을리가 없음

const dp = Array.from({ length: N }, () => new Array(N).fill(0));

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const dfs = (x, y) => {
    if (dp[x][y] !== 0) return dp[x][y];

    dp[x][y] = 1;
    let count = 0;

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

        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (board[x][y] < board[nx][ny]) {
            count = Math.max(count, dfs(nx, ny));
        }
    }

    return (dp[x][y] += count);
};

let answer = 0;

for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        answer = Math.max(answer, dfs(i, j));
    }
}

console.log(answer);

 

📌 설명 

판다가 이동할 수 있는 칸 수의 최대 값을 구하는 문제이다. 

 

규칙 : 판다는 현재 칸에 있는 대나무보다 더 많은 대나무가 있는 곳으로만 이동가능하다.

-> 모든 위치에서 dfs를 돌려서 최장거리를 구하는 것은 너무 많은 시간과 메모리가 들게 된다.

-> 판다는 더 대나무가 많은 곳으로만 갈 수 있으니까, (i, j) 위치에서 시작해서 갈 수 있는 칸의 최대값은 항상 같다.

-> (i, j) 값을 저장해놓고 사용하자! => dp 사용하기  

 

DFS : 더 대나무가 많은 칸으로 이동하기 위해 사용, 재귀로 구현

DP : 저장된 값이 있으면 사용하고, 없으면 dfs를 이용해서 구해서 저장하기

const dfs = (x, y) => {
    if (dp[x][y] !== 0) return dp[x][y];

    dp[x][y] = 1; // 시작하는 칸 한 칸을 추가해준다
    let count = 0; // 현재 위치에서 이동 가능한 칸의 최대값을 저장할 변수

    for (let i = 0; i < 4; i++) { // 상하좌우를 살펴보기
        const nx = x + dx[i];
        const ny = y + dy[i];

        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (board[x][y] < board[nx][ny]) { // 이전 위치보다 더 큰 값이면
            count = Math.max(count, dfs(nx, ny)); // nx,ny 위치에서 갈 수 있는 최대값과 / 다른 방향으로 갔을 때의 최대값 비교하기
        }
    }

    return (dp[x][y] += count); // i,j에서 이동 가능한 칸 수의 최대값
};

 

✅ 성공