백준 7562 JS 풀이

구하는 값

나이트가 이동해서 원하는 칸에 도달하기 위한 이동횟수

핵심 아이디어

다른 dfs기본문제랑 크게 다를것 없지만

1. 입력값에서 testcase 별로 나눠서 처리하기
2. 나이트의 이동 경로가 dx = [-2, -2, -1, 1, 2, 2, -1, 1], dy = [-1, 1, -2, -2, -1, 1, 2, 2]

이거 말고 특별한 것은 없었다.

코드

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