[JS] 백준 7562번 나이트의 이동

---

문제 링크

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

풀이 전략

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

나이트가 이동할 수 있는 경우의 수를 이전에 bfs를 이동하였을 때와 같이 배열을 생성한다. 그 이외에는 다른 bfs문제와 같다. 

코드 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const t = +input.shift();

solution(input);

function solution(arr) {
    let idx = 0;
    const dx = [1, 2, 2, 1, -1, -2, -2, -1];
    const dy = [2, 1, -1, -2, -2, -1, 1, 2];
    const answer = [];
    for (let i = 0; i < t; i++) {
        const l = +arr[idx++];
        const [curX, curY] = arr[idx++].split(" ").map(Number);
        const [tarX, tarY] = arr[idx++].split(" ").map(Number);
        const chess = Array.from({ length: l }, () => Array(l).fill(0));
        let queue = [];

        queue.push([curX, curY, 0]);

        while (queue.length) {
            const [X, Y, cnt] = queue.shift();
            if (X === tarX && Y === tarY) {
                answer.push(cnt);
                break;
            }
            for (let i = 0; i < 8; i++) {
                const nX = X + dx[i];
                const nY = Y + dy[i];

                if (
                    0 <= nX &&
                    nX < l &&
                    0 <= nY &&
                    nY < l &&
                    chess[nX][nY] === 0
                ) {
                    chess[nX][nY] = 1;
                    queue.push([nX, nY, cnt + 1]);
                }
            }
        }
    }

    console.log(answer.join("\n"));
}

 

회고

처음 제출할 때 시간초과가 날 것 같아 걱정했는데 생각외로 빠르게 처리되었다.

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)