https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
📌 작성한 코드
// 1600
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const K = Number(input[0]);
const [W, H] = input[1].split(" ").map(Number);
const board = [];
for (let i = 2; i < input.length; i++) {
board.push(input[i].split(" "));
}
const visited = Array.from({ length: H }, () => Array.from({ length: W }, () => new Array(K + 1).fill(false)));
const kx = [-2, -2, -1, -1, 1, 1, 2, 2];
const ky = [1, -1, 2, -2, 2, -2, 1, -1];
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const bfs = (startX, startY) => {
if (H === 1 && W === 1) return 0;
const queue = [];
queue.push([startX, startY, K, 0]);
visited[startX][startY] = true;
let idx = 0;
while (queue.length > idx) {
const [x, y, remain, count] = queue[idx++];
if (remain > 0) {
for (let i = 0; i < kx.length; i++) {
const nx = x + kx[i];
const ny = y + ky[i];
if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
if (!visited[nx][ny][remain - 1] && board[nx][ny] === "0") {
queue.push([nx, ny, remain - 1, count + 1]);
visited[nx][ny][remain - 1] = true;
}
}
if (nx === H - 1 && ny === W - 1) {
return count + 1;
}
}
}
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
if (!visited[nx][ny][remain] && board[nx][ny] === "0") {
queue.push([nx, ny, remain, count + 1]);
visited[nx][ny][remain] = true;
}
}
if (nx === H - 1 && ny === W - 1) {
return count + 1;
}
}
}
return -1;
};
console.log(bfs(0, 0));
📌 풀이
원숭이가 (0,0)에서 (H-1,W-1)까지 가는 최소 이동 거리를 구하는 문제이다. 이때 원숭이가 움직일 수 있는 방법은 2가지가 존재한다.
1. 말처럼 움직이기(체스의 나이트 처럼 움직이기), 단 k번만 움직일 수 있다.
2. 상하좌우 인접한 부분으로 움직이기. 이동 횟수에 제한이 없다.
그래서 이런 이동 방법을 이용해서 bfs를 구현해볼 것이다. 그런데 이 문제를 풀 때 주의해야 할 점이 있다. 바로 방문 배열의 형태이다.
일반적인 방문 배열은 맵과 똑같이 H * W 형태의 이차원 배열로 선언되어서, 해당 위치에 도달하면 방문 배열을 업데이트 해주는 방식으로 사용해왔다. 하지만 그 방법은 움직일 수 있는 방법이 단 1가지 일 때만 사용 가능하다. 이동하는 방법이 1가지일 때는 해당 위치에 도달한 첫번째 방법이 최소 거리 이동 방법인 것이 확실하기 떄문이다.
그러나 우리는 이 문제에서 1,2번 두가지의 방법을 사용할 수 있고, 그 말은 즉슨 1,2번을 언제 사용하느냐에 따라서 해당 위치까지 도달하는 최소 거리가 달라질 수 있다는 의미이다. 그렇다면 처음 도달했을 때 이동 거리가 최소의 이동 거리가 아닐 수 있기 때문에 우리는 그냥 방문 배열에 저장하지 않고, 현재 이동하는데 사용된 1번(말처럼 이동하기)방식을 몇번 사용해서 여기까지 도달했는지를 저장해야 한다. 그래서 우리는 방문 배열을 삼차원 배열로 선언할 것이다.
const visited = Array.from({ length: H }, () => Array.from({ length: W }, () => new Array(K + 1).fill(false)));
그리고 k번만 1번을 사용할 수 있으니까 k의 횟수가 남아있는 경우에만 말처럼 이동할 수 있도록 조건도 달아준다.
if (remain > 0) {
for (let i = 0; i < kx.length; i++) {
const nx = x + kx[i];
const ny = y + ky[i];
if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
if (!visited[nx][ny][remain - 1] && board[nx][ny] === "0") {
queue.push([nx, ny, remain - 1, count + 1]);
visited[nx][ny][remain - 1] = true;
}
}
if (nx === H - 1 && ny === W - 1) {
return count + 1;
}
}
}
그리고 h와 w가 1이라서 도착 지점이 곧 시작 지점인 경우의 예외 처리도 해주어야 한다. (따로 해주지 않으면 -1로 도달 불가능이 나온다.)
if (H === 1 && W === 1) return 0;
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/BFS] 백준 골드 4 : 3055 - 탈출 (1) | 2024.01.28 |
|---|---|
| [JavaScript/BFS] 백준 골드 3 : 14442 - 벽 부수고 이동하기 2 (0) | 2024.01.27 |
| [JavaScript/BFS] 백준 골드 4 : 13913 - 숨바꼭질 4 (0) | 2024.01.27 |
| [JavaScript/BFS] 백준 골드 3 : 2206 - 벽 부수고 이동하기 (1) | 2024.01.25 |
| [JavaScript/BFS] 백준 골드 4 : 4179 - 불! (2) | 2024.01.24 |