데스 나이트

문제

언어

  • JavaScript

순서도

  1. BFS 탐색

문제 풀이 step 1

  • 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 “데스 나이트”를 만들었습니다.
  • 데스 나이트가 있는 곳이 (r, c) 라면, (r - 2, c - 1), (r - 2, c + 1), (r, c - 2), (r, c + 2), (r + 2, c - 1), (r + 2, c + 1) 로 이동할 수 있습니다.
  • 크기가 N x N 인 체스판과 두 칸 (r1, c1), (r2, c2) 가 주어집니다.
  • 이 때, 데스 나이트가 (r1, c2) 에서 (r2, c2) 로 이동하는 최소 이동 횟수를 구하는 문제입니다.
  • 체스판의 행과 열은 0 번 부터 시작하며, 데스 나이트는 체스판 밖으로 벗어날 수 없습니다.

문제 풀이 step 2

  • 우선, N x N 크기의 2 차원 배열을 생성하고, 모든 칸을 -1 로 초기화합니다.
    • 이는 이동할 수 없는 경우 -1 을 출력하기 위함입니다.
  • 그리고 (r1, c1) 을 시작점으로 BFS 탐색을 수행합니다.
    • 탐색을 수행할 때, 방문처리 및 시작점으로부터의 거리를 표시하기 위한 distance 배열을 생성합니다.
    • 시작점으로부터 갈 수 있는 모든 노드를 방문하며, distance 배열을 채워줍니다.
  • BFS 탐색을 모두 마쳤으면, distance[r2][c2] 에 들어있는 값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

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

// 총 6 가지 방향
const dir = [
	[-2, -1],
	[-2, 1],
	[0, -2],
	[0, 2],
	[2, -1],
	[2, 1],
];

// 체스판을 벗어나는지 검사하는 함수
const isPossibleRoute = (n, x, y) => 0 <= x && x < n && 0 <= y && y < n;

// bfs 탐색 함수
const bfs = (n, distance, r1, c1, r2, c2) => {
	const queue = new Queue();

	distance[r1][c1] = 0;
	queue.enqueue([r1, c1]);
	while (!queue.isEmpty()) {
		const [fx, fy] = queue.dequeue();

		// 총 6 가지 방향 검사
		for (let i = 0; i < 6; i++) {
			const [tx, ty] = [fx + dir[i][0], fy + dir[i][1]];

			// 불가능한 경로 혹은 이미 방문한 경로라면 continue
			if (!isPossibleRoute(n, tx, ty)) continue;
			if (distance[tx][ty] !== -1) continue;

			// distance 배열 갱신
			distance[tx][ty] = distance[fx][fy] + 1;
			queue.enqueue([tx, ty]);
		}

		if (distance[r2][c2] !== -1) break;
	}
};

const solution = (input) => {
	const n = Number(input[0]);
	const [r1, c1, r2, c2] = input[1].split(" ").map(Number);

	const distance = Array.from({length: n}, () => Array(n).fill(-1));
	bfs(n, distance, r1, c1, r2, c2);

	return distance[r2][c2];
};

console.log(solution(input));