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

문제

문제풀이

나이트가 도착지까지 이동하는데 걸리는 시간을 반환하면 되는 문제입니다. 이때 이 거리는 최소가 됩니다.

따라서 BFS를 이용해서 풀면 되는 문제입니다.

다른 문제들과 달리 이동방향이 총 8개로 설정되어 있기 때문에 이 부분만 신경써주면 됩니다.

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

결과코드

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

let tc = Number(input.shift());

let l = 0,
    sx = 0,
    sy = 0,
    ex = 0,
    ey = 0;

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

for (let t = 0; t < tc; t++) {
    l = Number(input.shift());
    [sx, sy] = input.shift().split(' ').map(Number);
    [ex, ey] = input.shift().split(' ').map(Number);
    console.log(bfs(sx, sy));
}

function bfs(a, b) {
    let visited = Array.from(Array(l), () => Array(l).fill(false));

    let queue = [[a, b, 0]];
    visited[a][b] = true;

    while (queue.length) {
        let [x, y, cnt] = queue.shift();

        if (x === ex && y === ey) return cnt;

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

            if (nx < 0 || ny < 0 || nx >= l || ny >= l) continue;

            if (!visited[nx][ny]) {
                queue.push([nx, ny, cnt + 1]);
                visited[nx][ny] = true;
            }
        }
    }
}