백준 7562번 나이트의 이동 [JAVA]

문제

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

 

입력

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

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

 

 

출력

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

 

 

예제

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_BJ_7562_나이트의이동 {
    
    static class info {
        int x, y, cnt;
 
        public info(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    static int l, goalX, goalY;
    static int [][] map;
    
    static int [] dx = {-1,-2,-2,-1,1,2,2,1};
    static int [] dy = {-2,-1,1,2,2,1,-1,-2};
    
    static PriorityQueue<info> pq = new PriorityQueue<>(new Comparator<info>() {
 
        @Override
        public int compare(info o1, info o2) {
            return o1.cnt-o2.cnt;
        }
    });
 
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc = 0; tc<T;tc++) {
            l = Integer.parseInt(br.readLine());
            
            map = new int[l][l];
            
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            map[x][y]=1;
            pq.add(new info(x,y,0));
                
            st = new StringTokenizer(br.readLine());
            goalX = Integer.parseInt(st.nextToken());
            goalY = Integer.parseInt(st.nextToken());
            
            map[goalX][goalY]=2;
            
            bfs();
            pq.clear();
        }
        System.out.println(sb.toString());
    }
    
    public static void bfs() {
        
        while(!pq.isEmpty()) {
            info temp = pq.poll();
            
            if(temp.x==goalX && temp.y==goalY) {
                sb.append(temp.cnt+"\n");
                return;
            }
            
            for(int i=0;i<8;i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];
                
                if(range(nx,ny)) {
                    if(map[nx][ny]==0) {
                        map[nx][ny]=1;
                        pq.add(new info(nx,ny,temp.cnt+1));
                    }else if(map[nx][ny]==2) {
                        sb.append(temp.cnt+1+"\n");
                        return;
                    }
                }
            }
        }
        
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<l && y>=0 && y<l;
    }
 
}