#백준_7562 나이트의 이동 - Java 자바

#유형 : 그래프, BFS

# BFS의 기본 문제중 한 가지. 기존의 다른 탐색문제에서 나이트의 이동 범위만 수정해주면 해결할 수 있다.

 

package bj;
 
import java.awt.Point;
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 p7562 {
    static int moveX[] = {1,2,2,1,-1,-2,-2,-1};
    static int moveY[] = {-2,-1,1,2,2,1,-1,-2};
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int t=0; t<tc; t++) {
            int n = Integer.parseInt(br.readLine());
            int arr[][] = new int[n][n];
            int currentX, currentY, targetX, targetY;
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            currentX = Integer.parseInt(st.nextToken());
            currentY = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            targetX = Integer.parseInt(st.nextToken());
            targetY = Integer.parseInt(st.nextToken());
            
            Point start = new Point(currentX,currentY);
            Point target = new Point(targetX, targetY);
            
            bfs(start, target, arr);
        }
    }
 
    private static void bfs(Point start, Point target, int[][] arr) {
        // TODO Auto-generated method stub
        Queue<Point> queue =new LinkedList<Point>();
        queue.add(start);
        boolean visit[][] = new boolean[arr.length][arr.length];
        visit[start.y][start.x] = true;
        while(!queue.isEmpty()) {
            Point p = queue.poll();
            if(p.y==target.y && p.x==target.x) {
                System.out.println(arr[p.y][p.x]);
                return;
            }
            
            for(int d=0; d<8; d++) {
                int newY = p.y + moveY[d];
                int newX = p.x + moveX[d];
                if(0<=newX && newX<arr.length && 0<=newY && newY<arr.length && !visit[newY][newX]) {
                    visit[newY][newX] = true;
                    arr[newY][newX] = arr[p.y][p.x] + 1;
                    queue.add(new Point(newX,newY));
                }
            }
        }
    }
}