[백준] #1600 말이 되고픈 원숭이 문제 풀이 | G3 | Node.js |

문제 링크 :  https://www.acmicpc.net/problem/1600

문제 정보 

문제 해결

문제 개요

백준 1600번 말이 되고픈 원숭이 문제는 격자판에서 원숭이가 말의 이동을 일정 횟수(k번)만 사용할 수 있는 상황에서 (0,0)에서 (w-1, h-1)까지의 최단 거리를 구하는 문제입니다.

• 원숭이는 일반적으로 상, 하, 좌, 우로 이동할 수 있습니다.
• 단, 말의 움직임(체스 나이트의 이동 패턴)을 최대 k번까지 사용할 수 있습니다.
• 도착점에 도달할 수 없으면 -1을 반환합니다.

 

해결 방법

이 문제는 최단 거리 문제이므로 BFS(너비 우선 탐색)을 사용하여 해결하였습니다.

• 일반적인 최단 거리 문제에서는 visited 배열을 2차원으로 사용하지만, 이 문제에서는 말처럼 움직일 수 있는 횟수(k)가 추가된 3차원 방문 배열이 필요합니다.
• (x, y, 말 이동 횟수) 상태를 관리하여 BFS 탐색을 진행합니다.
• Queue를 활용하여 (현재 x좌료, 현재 y좌표, 현재까지 사용한 말 이동 횟수, 이동 거리)를 저장하고 탐색을 진행합니다.

 

최종 코드 

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

const k = Number(input[0]);
const [w, h] = input[1].split(" ").map(Number);
let arr = input.splice(2).map((line) => line.split(" ").map(Number));
let visited = Array.from(
  { length: h },
  () => Array.from({ length: w }, () => Array(k + 1).fill(false)) // 
);

const kMove = [
  [-2, -1],
  [-2, 1],
  [-1, -2],
  [-1, 2],
  [1, -2],
  [1, 2],
  [2, -1],
  [2, 1],
];

const nMove = [
  [0, -1],
  [0, 1],
  [1, 0],
  [-1, 0],
];

function bfs() {
  const queue = [];
  queue.push([0, 0, 0, 0]); //x, y, 말 이동 횟수, 이동 횟수
  visited[0][0][0] = true;
  let begin = 0;
  while (begin < queue.length) {
    const [cx, cy, kCheck, cnt] = queue[begin++];
    if (cx === w - 1 && cy === h - 1) return cnt;

    // 말 이동
    if (kCheck < k) {
      for (let [mx, my] of kMove) {
        const nx = cx + mx;
        const ny = cy + my;
        if (nx < 0 || nx >= w || ny < 0 || ny >= h || arr[ny][nx] == 1) continue;
        if (!visited[ny][nx][kCheck + 1]) {
          visited[ny][nx][kCheck + 1] = true;
          queue.push([nx, ny, kCheck + 1, cnt + 1]);
        }
      }
    }

    // 원숭이 이동
    for (let [mx, my] of nMove) {
      const nx = cx + mx;
      const ny = cy + my;
      if (nx < 0 || nx >= w || ny < 0 || ny >= h || arr[ny][nx] == 1) continue;
      if (!visited[ny][nx][kCheck]) {
        visited[ny][nx][kCheck] = true;
        queue.push([nx, ny, kCheck, cnt + 1]);
      }
    }
  }

  return -1;
}

console.log(bfs());

 

정리

3차원 방문 배열을 활용하여 BFS 탐색을 진행해야 하는 문제였고, 말의 의동 횟수를 관리하는 것이 핵심이었습니다.