작성 코드

import java.awt.*;
import java.io.*;
import java.util.*;

public class night_move_7562 {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCases; i++){
            int len = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int cx = Integer.parseInt(st.nextToken());
            int cy = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int tx = Integer.parseInt(st.nextToken());
            int ty = Integer.parseInt(st.nextToken());

            // 최소 움직여서 타겟지점으로 가는 함수
            int minMoves = getMinMoves(len, cx, cy, tx, ty);
            System.out.println(minMoves);
        }
    }

    public static int getMinMoves(int len, int cx, int cy, int tx, int ty) {
        int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1};
        int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};

        boolean[][] visited = new boolean[len][len];
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(cx, cy));
        visited[cx][cy] = true;

        int minMoves = 0;
        boolean foundTarget = false;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Point c = queue.poll();

                if (c.x == tx && c.y == ty) {
                    foundTarget = true;
                    break;
                }

                for (int j = 0; j < 8; j++) {
                    int nx = c.x + dx[j];
                    int ny = c.y + dy[j];

                    if (nx >= 0 && nx < len && ny >= 0 && ny < len && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.offer(new Point(nx, ny));
                    }
                }
            }

            if (foundTarget) {
                break;
            }

            minMoves++;
        }

        return minMoves;
    }

    public static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

로직 설명

자료구조

• Point 클래스: 좌표를 표현하는 클래스로, x와 y 좌표를 저장합니다.
• boolean[][] visited: 체스판의 각 칸을 방문한 여부를 저장하는 2차원 배열입니다.
• visited[x][y]가 true이면 (x, y) 좌표를 방문한 것을 의미합니다.
• Queue<Point> queue: BFS(Breadth-First Search) 알고리즘을 위한 큐입니다. 나이트가 이동하는 경로를 저장하고, 탐색을 위해 사용됩니다.

로직

• 입력값으로 주어진 테스트 케이스 수를 받습니다.
• 각 테스트 케이스마다 다음을 수행합니다.
• 체스판 크기 len을 입력받고, 현재 위치(cx, cy)와 목표 위치(tx, ty)를 입력받습니다.
• getMinMoves 함수를 호출하여 최소 움직임 수를 구합니다.
• 최소 움직임 수를 출력합니다.
• getMinMoves 함수는 BFS 알고리즘을 사용하여 최소 움직임 수를 계산합니다.
• dx와 dy 배열에는 나이트가 이동할 수 있는 8가지 방향의 상대적인 좌표 변화가 저장되어 있습니다.
• visited 배열을 초기화하고, 큐에 현재 위치를 넣고 방문 표시를 합니다.
• minMoves 변수를 0으로 초기화하고, 목표 위치를 찾았는지를 나타내는 foundTarget 변수를 false로 설정합니다.
• 큐가 비어있지 않은 동안 다음을 반복합니다.
• 현재 큐의 크기만큼 반복하여 현재 위치를 꺼냅니다.
• 현재 위치가 목표 위치와 일치하는지 확인합니다. 일치하면 foundTarget를 true로 설정하고 반복문을 종료합니다.
• 8가지 방향으로 나이트가 이동할 수 있는 위치를 계산하고, 범위 내에 있고 방문하지 않았다면 큐에 넣고 방문 표시를 합니다.
• 목표 위치를 찾지 못했다면 minMoves를 증가시킵니다.
• 최소 움직임 수인 minMoves를 반환합니다.

자바스크립트

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

function getMinMoves(len, cx, cy, tx, ty) {
  const dx = [-1, -2, -2, -1, 1, 2, 2, 1];
  const dy = [-2, -1, 1, 2, 2, 1, -1, -2];

  const visited = Array.from({ length: len }, () => Array(len).fill(false));
  const queue = [];
  queue.push(new Point(cx, cy));
  visited[cx][cy] = true;

  let minMoves = 0;
  let foundTarget = false;

  while (queue.length > 0) {
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const c = queue.shift();

      if (c.x === tx && c.y === ty) {
        foundTarget = true;
        break;
      }

      for (let j = 0; j < 8; j++) {
        const nx = c.x + dx[j];
        const ny = c.y + dy[j];

        if (
          nx >= 0 &&
          nx < len &&
          ny >= 0 &&
          ny < len &&
          !visited[nx][ny]
        ) {
          visited[nx][ny] = true;
          queue.push(new Point(nx, ny));
        }
      }
    }

    if (foundTarget) {
      break;
    }

    minMoves++;
  }

  return minMoves;
}

function main() {
  const readline = require("readline");
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
  });

  rl.question("", (testCases) => {
    for (let i = 0; i < testCases; i++) {
      rl.question("", (len) => {
        rl.question("", (coords1) => {
          const [cx, cy] = coords1.split(" ").map(Number);

          rl.question("", (coords2) => {
            const [tx, ty] = coords2.split(" ").map(Number);

            const minMoves = getMinMoves(len, cx, cy, tx, ty);
            console.log(minMoves);

            if (i === testCases - 1) {
              rl.close();
            }
          });
        });
      });
    }
  });
}

main();

파이썬

from collections import deque

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def getMinMoves(len, cx, cy, tx, ty):
    dx = [-1, -2, -2, -1, 1, 2, 2, 1]
    dy = [-2, -1, 1, 2, 2, 1, -1, -2]

    visited = [[False] * len for _ in range(len)]
    queue = deque()
    queue.append(Point(cx, cy))
    visited[cx][cy] = True

    minMoves = 0
    foundTarget = False

    while queue:
        size = len(queue)

        for _ in range(size):
            c = queue.popleft()

            if c.x == tx and c.y == ty:
                found