나이트의 이동

문제

언어

  • JavaScript

문제 풀이 step 1

  • 이번 문제는 기존의 BFS 문제와 크게 다른점은 없습니다.
  • 기존에 만들어 놓은 간단한 큐가 있어서 재활용했습니다.
  • 우선 주어지는 체스판의 크기에 따라서 -1 로 초기화한 이차원 배열을 생성합니다.
    • 그리고 주어지는 시작점에서 BFS 탐색을 실시합니다.
    • 그리고 문제에서 주어지는 도착점에 도달하면 탐색을 종료합니다.
  • 저는 방문 처리를 탐색 시마다 시작점으로부터의 거리를 기록하는 방식으로 대신했습니다.

소스 코드 1

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

// 간단한 큐 구현
class Queue {
	constructor() {
		this.backet = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(data) {
		this.backet[++this.front] = data;
	}

	dequeue() {
		if (!this.isEmpty()) return this.backet[++this.rear];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

class Dot {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
}

const BFS = (n, start, end, arr) => {
	// 나이트의 이동 방향
	const cx = [2, 1, -1, -2, -2, -1, 1, 2];
	const cy = [1, 2, 2, 1, -1, -2, -2, -1];
	const queue = new Queue();

	arr[start.x][start.y] = 0;
	queue.enqueue(start);
	while (!queue.isEmpty() && arr[end.x][end.y] === -1) {
		const from = queue.dequeue();
		const NEXT_MARK = arr[from.x][from.y] + 1;

		for (let i = 0; i < 8; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);

			if (
				0 <= to.x &&
				to.x < n &&
				0 <= to.y &&
				to.y < n &&
				arr[to.x][to.y] === -1
			) {
				arr[to.x][to.y] = NEXT_MARK;
				queue.enqueue(to);
			}
		}
	}
};

const solution = (input) => {
	let index = 0;
	let t = parseInt(input[index++]);

	let res = "";
	while (t-- > 0) {
		let n = parseInt(input[index++]);
		const start = new Dot(...input[index++].split(" ").map(Number));
		const end = new Dot(...input[index++].split(" ").map(Number));

		// -1 로 초기화한 n x n 크기의 배열
		const arr = Array.from({length: n}, () => Array(n).fill(-1));
		BFS(n, start, end, arr);

		res += `${arr[end.x][end.y]}\n`;
	}

	return res;
};

console.log(solution(input));