백준 7562 JS풀이

구하는 값

나이트를 이동해서 도착점까지의 최소거리

핵심 아이디어

가중치가 없는 그래프이므로 BFS를 통해서 최단 거리를 구해줌

구현방법

나이프가 이동할 수 있는 4방향 총 8가지의 경우를 dx,dy로 표현
que를 구현해서 시작점을 que에 넣고 deque하며 다음 노드값들 중 방문하지 않은 노드를 que에 enque하며 visited에 root노드부터의 거리를 대입함
que의 size가 0 || 목적지 도달 하면 종료

코드

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

class Que {
    constructor() {
        this.que = [];
        this.head = 0;
        this.tail = 0;
    }
    enque(v) {
        this.que[this.tail++] = v;
    }

    deque() {
        const v = this.que[this.head];
        delete this.que[this.head++];
        return v;
    }

    size() {
        return this.tail - this.head;
    }
}

let ts = Number(input[0]);
let line = 1;

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

let ans = "";
while (ts--) {
    const l = Number(input[line++]);
    const [y1, x1] = input[line++].split(" ").map(Number);
    const [y2, x2] = input[line++].split(" ").map(Number);

    const queue = new Que();
    const visited = Array.from({ length: l }, () => new Array(l).fill(0));

    function bfs(y, x) {
        queue.enque([y, x]);
        visited[y][x] = 1;

        while (queue.size() !== 0) {
            const [cy, cx] = queue.deque();

            if (cy === y2 && cx === x2) return visited[cy][cx];

            for (let i = 0; i < 8; i++) {
                const nx = cx + dx[i],
                    ny = cy + dy[i];

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

                if (visited[ny][nx] === 0) {
                    visited[ny][nx] = visited[cy][cx] + 1;
                    queue.enque([ny, nx]);
                }
            }
        }
    }

    ans += bfs(y1, x1) - 1 + "\n";
}

console.log(ans);