[Java] 백준 7562 나이트의 이동

https://www.acmicpc.net/problem/7562

난이도

실버1

문제

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

입력

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

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

출력

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

내 코드

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

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
        int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

        for(int tc = 0; tc < T; tc++){
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int endX = Integer.parseInt(st.nextToken());
            int endY = Integer.parseInt(st.nextToken());

            Queue<int[]> q = new LinkedList<>();
            boolean[][] visited = new boolean[N][N];
            q.add(new int[]{startX, startY, 0});
            visited[startX][startY] = true;

            while(!q.isEmpty()){
                int[] now = q.poll();
                if(now[0] == endX && now[1] == endY){
                    sb.append(now[2]).append("\n");
                    break;
                }
                
                for(int i = 0; i < 8; i++){
                    int nx = now[0] + dx[i];
                    int ny = now[1] + dy[i];
                    if(nx < 0 || nx >= N || ny < 0 || ny >= N){
                        continue;
                    }if(visited[nx][ny]){
                        continue;
                    }
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny, now[2] + 1});
                }
            }
        }
        
        System.out.println(sb);
    }
}

dx, dy만 잘 정하고 일반적인 BFS로 풀면 되는 간단한 문제였다.