문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

5
28
0

나의 코드

let input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));
input.shift();
// 하나의 테스트 케이스마다 solution 함수의 인자로 전달
while (input.length > 0) {
  const testCase = input.splice(0, 3);
  const size = testCase[0][0];
  const start = testCase[1];
  const end = testCase[2];
  console.log(solution(size, start, end));
}

function solution(size, start, end) {
// 한번에 총 8개의 방향으로 이동 가능함을 감안하여 순회할 배열 선언
  const dx = [-2, -2, 2, 2, -1, -1, 1, 1];
  const dy = [-1, 1, -1, 1, -2, 2, -2, 2];
  // 만약 출발점과 도착점이 같으면 움직이지 않고 바로 0 반환 (예외 처리)
  if (start[0] === end[0] && start[1] === end[1]) return 0;
  
  // 최단 거리를 구하기 위해 한 걸음씩 돌아가며 내딛는 bfs로 해결하려 함
  function bfs(x, y) {
   // 빈 배열 queue 선언하고 start 배열 queue에 push하고 시작
    let queue = [];
    queue.push(start);
 // test case 별 사이즈의 정사각형 보드판 선언. 각 원소는 0으로 채움.
    let board = [...Array(size)].map((row) =>
      [...Array(size)].map((v) => (v = 0))
    );
    // 도착점에 도달하는 경우가 생길 때까지만 while문을 돌림
    while (true) {
      if (board[end[0]][end[1]] > 0) return board[end[0]][end[1]];
      // queue에서 가장 먼저 빠져나오는 x,y 주변을 탐색해야 함
      [x, y] = queue.shift();
      // dx와 dy를 순회하여 nx, ny 선언
      for (let i = 0; i < 8; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];
        
 // 지옥의 if문 시작. 보드 밖으로 나가면 무시하고 다음 방향 탐색하러 ㄱㄱ
        if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue;
        // ⭐️ 이미 가본 곳이라면? 탐색할 필요 없으므로 역시 continue 
        if (board[nx]?.[ny] > 0) continue; 
  // 지옥의 if문을 통과했다면 당신은 방문 가능한 인접 노드! 1만큼 증가시킨 숫자로 방문 처리
        board[nx][ny] = board[x][y] + 1;
  // 방문 가능한 인접 노드이므로 queue에 push함
        queue.push([nx, ny]);
      }
    }
  }
  return bfs(start[0], start[1]);
}

내가 또 다른 BFS를 풀 수 있게 될 줄이야!! 아주 감격스럽다~!~!
어제 프로그래머스에서 풀었던 게임맵 최단 거리 문제랑 비슷한 논리로 풀어내니 통과할 수 있었다. 어제 DFS BFS 빡세게 공부한 보람이 무지무지 있군!! 생각보다 이 문제를 빨리 해결할 수 있었던 것 보면 어제 8시간 동안 2문제 밖에 못 풀긴 했지만 정말 귀중한 시간이었던 것 같다. 물론 더 난이도가 높아지면 계속계속 갈고 닦아야겠지??!

그런데 중간에 한 번 지옥의 if문 부분에서 실수해서 시간 초과 되었었다. 같은 실수 안 하도록 기록하고 넘어가자!! 코드에서 ⭐️표 친 부분이다.

if (board[nx]?.[ny] === 1) continue; // 시간 초과
if (board[nx]?.[ny] > 0) continue; // 통과

처음에는 1만 아니면 모두 방문해도 되는 것으로 잘못 생각하고 제출했다. 딱 한 번 방문해본 곳이면 가지 말라는 의미인데 지금 복기해보니 무슨 논리로 저렇게 했는지 모르겠다.
하지만 그냥 단순 실수?라고 하기에는 분명 헷갈렸던 부분이 있었다. 다시 가본 곳이면 가지 말아야 하는가? 가지 말아야 한다. 갈 필요가 없다! 그런데 이미 가본 곳이면 1이 될 수도 있고 더 큰 숫자가 될 수도 있다. 1번이 아니라 2번이든 3번이든 1번 이상 가본 곳이면 지나치도록 하자!

아아 하여튼 통과하니 뿌듯하다 ㅋㅋㅋㅋㅋㅋ (만족하지마 재스민 dfs와 bfs는 여기서 끝이 아니야)