백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 11048 , 이동하기 [dp]

백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 11048 , 이동하기 

 

 

 

문제 출처

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

11048번: 이동하기

 

 

 

풀이

dp로 풀어야 통과하고 bfs 로 돌려보니 메모리 초과가 났다.

 

근데 최단거리 구하는 문제는 아니라서 bfs로 풀기는 적합하지 않다. 그냥 연습삼아 해봤음

 

 

 

 

 

 

 

 

 

 

정답

 

 

1. dp

 

 

 

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

const [N, M] = input.shift().trim().split(" ").map(Number);
let arr = [];
input.map((v) => {
  arr.push(v.trim().split(" ").map(Number));
});

dp = [];
for (let i = 0; i < arr.length + 1; i++) {
  dp.push([...new Array(arr[0].length + 1)].fill(0));
}

for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= M; j++) {
    dp[i][j] =
      arr[i - 1][j - 1] +
      Math.max(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
  }
}
console.log(dp[N][M]);

 

 

 

 

 

 

2. BFS (메모리 초과 발생)

 

 

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

const [N, M] = input.shift().trim().split(" ").map(Number);
let arr = [];

input.map((v) => {
  arr.push(v.trim().split(" ").map(Number));
});

dr = [
  [1, 0],
  [0, 1],
  [1, 1],
];
dq = [[0, 0, 0]];
check = [];
for (let i = 0; i < arr.length; i++) {
  check.push([...new Array(arr[0].length)].fill(0));
}

while (dq.length !== 0) {
  let [Z, X, Y] = dq[0];
  dq = dq.splice(1);
  for (let i of dr) {
    let [mx, my] = [X + i[0], Y + i[1]];
    if (mx >= N || my >= M) continue;
    if (0 < mx < N && 0 < my < M) {
      MZ = Z + arr[mx][my];
      if (check[mx][my] <= MZ) {
        check[mx][my] = MZ;
        dq.push([MZ, mx, my]);
      }
    }
  }
}

let result = arr[0][0] + check[N - 1][M - 1];
console.log(result);