🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [tc, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');
// 1. 나이트의 이동 방향 정의
const dx = [1, 1, 2, 2, -1, -1, -2, -2];
const dy = [2, -2, 1, -1, 2, -2, 1, -1];
for (let t = 0; t < Number(tc); t++) {
// 2. tc 분리
const [l, start, end] = [
Number(inputs[t * 3]),
inputs[t * 3 + 1].split(' ').map((it) => Number(it)),
inputs[t * 3 + 2].split(' ').map((it) => Number(it)),
];
// 3. map 선언
const map = Array.from({ length: l }, () => Array(l).fill(0));
map[start[0]][start[1]] = 1;
// 4. bfs 구현
const bfs = () => {
const q = [[start[0], start[1], 0]];
while (q.length) {
const [x, y, cnt] = q.shift();
if (x === end[0] && y === end[1]) return cnt;
for (let i = 0; i < 8; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= l || ny >= l) continue;
// 5. 방문체크
if (map[nx][ny] === 0) {
map[nx][ny] += 1;
q.push([nx, ny, cnt + 1]);
}
}
}
};
console.log(bfs());
}🟢 풀이
⏰ 소요한 시간 : 2시간 쓰고 못풀어서 답봄
하.. 일단 나이트가 어떻게 이동하는지 몰라서 좀 알아봤다.
나이트는 기본적으로 L자 모양으로 이동할 수 있다고 한다.
그래서 문제를 보자마자 이동을 L자 모양 총 8방향으로 해주고, 최단 거리를 구해야겠다는 생각으로 bfs 풀이를 진행했다.
테스트 케이스가 세번이라 세번의 for문 안에 모든코드를 몰아넣었는데 그냥 전역변수로 선언하는게 나았을뻔 ... 코드가 너무 지저분한 것 같다.
각설하고 1번 위치에서 bfs로 뻗어나갈 8개의 방향을 정의해준 후 2번 위치에서 테스트 케이스를 정제하여 사용하기 좋은 자료형/구조로 변경해준다.
3번 위치에서 체스판의 크기에 맞는 맵을 만들어주고 모든 위치를 미방문 상태인 0으로 초기화 해준다. 현재 말이있는 위치는 내가 이미 밟고있는 땅이기 때문에 바로 방문상태인 1로 변경해줬다.
4번 위치에서 본격적으로 bfs 함수를 구현한다. 큐가 빌때까지 반복을 수행하는데 보통의 bfs는 (0,0)에서 (n,n)위치로 가고 bfs의 맨 하단에 (n,n) 위치를 리턴하는 형식인데 이 문제는 도착지에 도착했으면 종료해야하기 때문에 만약 도착지와 동일하다면 최단거리를 리턴해준다.
만약 도착지와 동일하지 않다면 기존 상하좌우 4방향으로 돌아주던 bfs방식을 응용해 8개의 방향으로 돌아준다.
그 후 범위를 벗어난다면 continue, 범위를 벗어나지 않는다면 해당 위치를 방문표시 해주고 큐에 bfs를 수행할 새로운 좌표값을 넣어준다.
나는 보통 최단거리를 체크할때 그냥 맵에 숫자를 넣어줬는데 이 문제는 그렇게 풀면 안된다. 왜인지 이해가 될듯 안될듯 하다.. 처음에는 5번 위치에서 큐에 값을 넣는것과 맵에 숫자를 1증가해주는 코드가 같이 있으니까 map[nx][ny] === cnt이 아닐까 싶었는데 생각해 보니 map[nx][ny] 안은 그 위치의 방문체크고 cnt는 내가 큐에 몇번 넣었느냐니까 다를 수 있다고 이해했다. 근데 난 늘 이렇게 풀어왔던 터라 너무 이해하기 어려웠다. ㅠㅠ 복습을 여러번 해야될 듯
🔵 Ref
