백준 7562: 나이트의 이동

문제

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

입력

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

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

출력

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

 

---

package com.company.ch9BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class KnightMovement {

    public static void main(String[] args) throws IOException {
        StringBuffer sb = new StringBuffer();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

         int[] dx = {-1,-2,-2,-1,1,2,2,1};
         int[] dy = {-2,-1,1,2,2,1,-1,-2};
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for (int i = 0; i < num; i++) {

            int length = Integer.parseInt(br.readLine());
            int[][] arr = new int[length][length];
            boolean[][] visit = new boolean[length][length];
            Queue<Point> qu = new LinkedList<>();
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken(" "));
            int m = Integer.parseInt(st.nextToken(" "));
 
            st = new StringTokenizer(br.readLine());

            int on = Integer.parseInt(st.nextToken(" "));  //목적지 x좌표
            int om = Integer.parseInt(st.nextToken(" "));  //목적지 y좌표
            
            
            arr[n][m] = 1;
            visit[n][m] = true;
            qu.offer(new Point(n, m));

            while(true){
                Point p =qu.poll();

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



                    if(nx<0 || nx>=length || ny<0 || ny>= length) continue;

                    if(!visit[nx][ny]){
                        qu.offer(new Point(nx, ny));
                        visit[nx][ny] = true;
                        arr[nx][ny] = arr[p.x][p.y] +1;
                    }
                }

                if(p.x == on && p.y ==om){
                    sb.append(arr[p.x][p.y]-1).append('\n');
                    break;
                }

            }

        }
        System.out.println(sb);
    }
    static class Point{
        int x;
        int y;

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

평범한 BFS 문제였다..! 이동할 수 있는 칸이 8칸임을 주의하자.