[백준][백트래킹] 1103 게임 NodeJs 구현

목차

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

문제

 

 

문제 구현 방향

그냥 단순히 백트래킹을 하게 되면 dfs의 무수한 호출로 인해 메모리 초과가 나게 된다.

따라서 dp를 이용해서 풀어주어야 하는 문제이다. 괜히 골드 1이 아니었다..

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [N, M] = input[0].trim().split(" ").map(Number);
let board = Array.from({ length: N }, () => Array(M));
let visit = Array.from({ length: N }, () => Array(M).fill(0));
let dp = Array.from({ length: N }, () => Array(M).fill(0));
let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];

function dfs(x, y) {
  if (x >= M || x < 0 || y >= N || y < 0 || board[y][x] === 0) return 0;
  if (visit[y][x]) {
    console.log(-1);
    process.exit(0);
  }
  if (dp[y][x] !== 0) return dp[y][x];

  visit[y][x] = 1;

  let s = board[y][x];

  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i] * s;
    let ny = y + dy[i] * s;
    dp[y][x] = Math.max(dp[y][x], dfs(nx, ny) + 1);
  }

  visit[y][x] = 0;
  return dp[y][x];
}

for (let i = 1; i < input.length; i++) {
  let ar = input[i].trim().split("");
  for (let j = 0; j < ar.length; j++) {
    board[i - 1][j] = ar[j] === "H" ? 0 : +ar[j];
  }
}

let ans = dfs(0, 0);
console.log(ans);