[백준] 7562 나이트의 이동 - javascript
📌 문제
https://www.acmicpc.net/problem/7562
📌 풀이
let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let tc = Number(input[0]);
let index = 1;
for (let i = 0; i < tc; i++) {
let board_size = Number(input[index]);
let board = new Array(board_size);
for (let j = 0; j < board.length; j++) {
board[j] = new Array(board_size).fill(0);
}
let start_x = Number(input[index + 1].split(" ")[0]);
let start_y = Number(input[index + 1].split(" ")[1]);
let end_x = Number(input[index + 2].split(" ")[0]);
let end_y = Number(input[index + 2].split(" ")[1]);
board[start_x][start_y] = 1;
function BFS() {
let L = 0;
let dx = [2, 2, -2, -2, 1, 1, -1, -1];
let dy = [1, -1, 1, -1, 2, -2, 2, -2];
let queue = [];
queue.push([start_x, start_y]);
while (queue.length) {
let len = queue.length;
for (let i = 0; i < len; i++) {
let v = queue.shift();
if (v[0] === end_x && v[1] === end_y) {
return L;
}
for (let i = 0; i < 8; i++) {
let nx = v[0] + dx[i];
let ny = v[1] + dy[i];
if (
nx >= 0 &&
nx < board_size &&
ny >= 0 &&
ny < board_size &&
board[nx][ny] === 0
) {
board[nx][ny] = 1;
queue.push([nx, ny]);
}
}
}
L++;
}
}
console.log(BFS());
index += 3;
}
✔ 알고리즘 : BFS
✔ 나이트가 이동할 수 있는 방향은 8가지이므로 dx,dy에 8개값을 넣는다
✔ input으로부터 받은 start_x,start_y값을 큐에 집어넣으면서 BFS탐색 시작
✔ board[a][b]가 1인경우는 탐색중인 현재 a,b좌표는 탐색완료상태 라는 뜻
✔ board의 범위를 벗어나지 않고 board[nx][ny]가 0인 경우만 탐색 -> 방문처리 해주고 queue에 push
✔ L을 통해 이동횟수 count하고 queue에서 shift했을 때 도착지점의 좌표와 같으면 L(이동횟수) return
✔ 난이도 : 백준기준 실버2
Author And Source
이 문제에 관하여([백준] 7562 나이트의 이동 - javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/백준-나이트의-이동-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)