[JavaScript/BFS] 백준 실버 1 : 7562 - 나이트의 이동

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

7562번: 나이트의 이동

---

📌 작성한 코드 

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

const dx = [-2, -1, -2, -1, 1, 2, 1, 2];
const dy = [1, 2, -1, -2, -2, -1, 2, 1];

const T = parseInt(input.shift(), 10);

for (let i = 0; i < T; i++) {
    const N = parseInt(input.shift(), 10);
    const [cX, cY] = input.shift().split(" ").map(Number);
    const [dX, dY] = input.shift().split(" ").map(Number);

    const visited = Array.from({ length: N }, () => new Array(N).fill(false));

    const bfs = () => {
        const queue = [];
        queue.push([cX, cY, 0]);

        let idx = 0;
        while (queue.length > idx) {
            const [x, y, count] = queue[idx++];
            visited[x][y] = true;

            for (let i = 0; i < 8; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny, count + 1]);
                }
                if (nx === dX && ny === dY) return count + 1;
            }
        }
    };

    if (cX === dX && cY === dY) console.log(0);
    else console.log(bfs());
}

 

📌 풀이 

어렵지 않은 bfs 문제이다. 보통 bfs를 적용할 때는 상하좌우를 보고 이동하곤 했는데, 체스가 이동 가능한 위치만 더 추가해서 다른 bfs 풀듯 똑같이 풀어주면 된다. 시작 위치에서 bfs 탐색을 출발하고, 도착하고자 하는 위치에 도달하면 현재까지의 이동 횟수를 출력해주면 된다. 

const dx = [-2, -1, -2, -1, 1, 2, 1, 2];
const dy = [1, 2, -1, -2, -2, -1, 2, 1];

 

 

✅ 성공