[JavaScript/BFS] 백준 골드 3 : 1600 - 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

---

📌 작성한 코드 

// 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;

 

✅ 성공