[BOJ 1937] 욕심쟁이 판다

문제

욕심쟁이 판다

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

 

 

풀이

설명

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

 

규칙은 다음과  같습니다.

• 판다의 초기 위치는 어떤 칸이든 될 수 있습니다.
• 상, 하, 좌, 우로 인접한 칸 중 하나로 이동합니다.
• 새로 이동하는 칸은 이전 칸보다 대나무가 많아야 합니다.

 

그래프 탐색과 DP를 이용해 해결할 수 있습니다.

 

dp[x][y]는 (x, y)에서 시작했을 때, 이동할 수 있는 칸의 수의 최댓값입니다.

 

다음 칸의 위치를 (nx, ny)라고 할 때, 점화식은 다음과 같습니다.

dp[x][y]는 다음 두 값 중 최댓값입니다.

• dp[x][y]
• dp[nx][ny] + 1

 

모든 칸에서 그래프 탐색을 진행하고, 각 칸에 대한 dp 값을 업데이트합니다.

 

예시 코드

function solution() {
  const n = Number(input());
  const board = Array.from({ length: n }, () => input().split(" ").map(Number));

  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  const dx = [0, -1, 0, 1];
  const dy = [1, 0, -1, 0];

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

  return maxDays;

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

    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[nx][ny] <= board[x][y]) continue;

      dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
    }

    return dp[x][y];
  }
}