문제
풀이
I x I 행렬에서, 나이트의 위치에서 목표 위치까지 얼마나 빨리 갈 수 있는지를 구하는 문제이다.
최단경로를 구하면 되므로 BFS를 사용해보자.
나이트가 이동 가능한 위치는 그림과 같다.
나이트가 동일한 위치를 두 번 방문하는 것은 다른 위치로 이동했다가 다시 돌아온 경우이므로,
이를 방지하기 위해 visit 행렬을 통해서 이전 위치로 되돌아가는 경우를 배제한다.
나이트는 총 8방향으로 이동할 수 있으므로, 나이트의 현재 위치를 기준으로 8개 방향의 이동 가능성을 조회하면 된다.
const sol = (input) => {
const N = +input[0];
let idx = 1; // 입력 처리를 위해 input의 인덱스를 조회하는 변수.
let result = "";
function bfs(knight, target, I) {
const queue = [];
queue.push(knight);
const visit = Array.from({ length: I }, () => Array(I).fill(0));
visit[knight[0]][knight[1]]=1;
const dx = [-2, -1, 1, 2, 2, 1, -1, -2]; // dx, dy는 나이트가 이동 가능한 좌표.
const dy = [1, 2, 2, 1, -1, -2, -2, -1];
while (queue.length) {
const [x, y] = queue.shift();
if (x === target[0] && y === target[1]) { // (x,y) 좌표 값이 target에 도달했으면 즉시 종료.
result += `${visit[x][y] - 1}\n`; // 시작 위치 값을 0이 아닌 1로 설정했으므로, 최종 도착 값에서 1을 빼준다.
break;
}
for (let i = 0; i < 8; i++) {
const [nx, ny] = [x + dx[i], y + dy[i]];
if (nx < 0 || ny < 0 || nx >= I || ny >= I) continue;
if (!visit[nx][ny]) { // 만약 이미 방문을 한 위치라면 조회하지 않는다.
visit[nx][ny] = visit[x][y] + 1; // visit[x][y]는 (x,y)까지의 최단경로이므로, 1을 더해주면 (nx,ny)까지의 최단경로.
queue.push([nx, ny]);
}
}
}
}
for (let i = 0; i < N; i++) { // N개 테스트 케이스를 순차적으로 테스트한다.
const I = +input[idx++];
const knight = input[idx++].split(" ").map((v) => +v);
const target = input[idx++].split(" ").map((v) => +v);
bfs(knight, target, I);
}
return result;
};
// 백준에서 입력을 받는 코드
const input = [];
require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
console.log(sol(input));
process.exit();
});
'DS & Algorithm > baekjoon' 카테고리의 다른 글
[백준] 16947번 서울 지하철 2호선 - JavaScript(NodeJS) (0) | 2021.05.29 |
---|---|
[백준] 16929번 Two Dots - JavaScript(NodeJS) (0) | 2021.05.29 |
[백준] 7576번 토마토 - JavaScript(NodeJS) (0) | 2021.05.28 |
[백준] 2178번 미로 -JavaScript(NodeJS) (0) | 2021.05.28 |
[백준] 13023번 ABCDE - JavaScript(NodeJS) (0) | 2021.05.27 |