[백준][bfs] 1600 말이 되고픈 원숭이 NodeJs 구현

     

목차

 

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

문제

 

 

문제 구현 방향

탐색 범위 때문에 그냥 dfs 백트래킹을 사용하면 시간 초과가 난다. 따라서 처음에 dp로 접근을 했지만

한 인덱스로만 탐색을 하기 때문에 틀리게 된다....

 

 

 

문제 풀이

정답은 bfs였다. 능력까지 추가해서 visit 배열을 3차원 배열로 만들고 똑같이 bfs를 적용해 주면 된다.

핵심 로직은 아래와 같다.

 

Js로 3차원 배열 구현 방법

let visit = Array.from({ length: M + 1 }, () =>
  Array.from({ length: N + 1 }, () => Array(K + 2).fill(0))
);

 

 

bfs시 주의점

 if (board[ny][nx] || visit[ny][nx][cnt + 1]) continue;
    visit[ny][nx][cnt + 1] = visit[y][x][cnt] + 1;


if (board[ny][nx] || visit[ny][nx][cnt]) continue;
	visit[ny][nx][cnt] = visit[y][x][cnt] + 1;

 

 

 

코드 구현

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

let K = +input[0];
let idx = 2;
let board = [];
let [N, M] = input[1].trim().split(" ").map(Number);

let visit = Array.from({ length: M + 1 }, () =>
  Array.from({ length: N + 1 }, () => Array(K + 2).fill(0))
);
let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];

let horse = [
  [2, 1],
  [1, 2],
  [2, -1],
  [-1, 2],
  [-1, -2],
  [-2, -1],
  [-2, 1],
  [1, -2],
];

while (idx < input.length) {
  let t = input[idx].trim().split(" ").map(Number);
  board.push(t);
  idx++;
}
let ans = 9999999;
function searching(Sx, Sy) {
  let queue = [];
  queue.push([Sx, Sy, 0]);
  visit[Sy][Sx][0] = 1;
  while (queue.length) {
    let [x, y, cnt] = queue.shift();
    for (let [sx, sy] of horse) {
      if (cnt >= K) break;
      let nx = x + sx;
      let ny = y + sy;
      if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
      if (board[ny][nx] || visit[ny][nx][cnt + 1]) continue;
      visit[ny][nx][cnt + 1] = visit[y][x][cnt] + 1;
      queue.push([nx, ny, cnt + 1]);
    }

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
      if (board[ny][nx] || visit[ny][nx][cnt]) continue;
      visit[ny][nx][cnt] = visit[y][x][cnt] + 1;
      queue.push([nx, ny, cnt]);
    }
  }
}
searching(0, 0);
for (let i = 0; i <= K; i++) {
  if (visit[M - 1][N - 1][i] != 0) ans = Math.min(ans, visit[M - 1][N - 1][i]);
}

if (ans === 9999999) console.log(-1);
else console.log(ans-1);