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

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

 

Solution 

package SILVER;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 나이트의이동 {
    static int[][] dir = new int[][]{{-2,-1},{-1,-2},{2,-1},{1,-2},{1,2},{2,1},{-2,1},{-1,2}};
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int testcase=0; testcase<T; testcase++){
            int N = Integer.parseInt(br.readLine());
            visit = new boolean[N][N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int targetx = Integer.parseInt(st.nextToken());
            int targety = Integer.parseInt(st.nextToken());// 입력받기

            Queue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]);
            q.add(new int[]{x, y, 0});
            visit[x][y] = true;
            int result =0;

            while(!q.isEmpty()){
                int[] curr = q.poll();
                int curr_x =  curr[0];
                int curr_y = curr[1];

                if(curr_x == targetx && curr_y == targety){
                    result = curr[2];
                    break;
                }

                for(int k =0; k<8; k++){
                    int r = curr_x + dir[k][0];
                    int c = curr_y + dir[k][1];
                    if(r>=0 && c>=0 && r<N&& c<N && !visit[r][c]){
                        visit[r][c] = true;
                        q.add(new int[]{r,c,curr[2]+1});
                    }
                }
            }
            System.out.println(result);
        }
    }
}

 

Priority Queue를 사용하여 cnt (이동하는 횟수)가 가장 적은 값이 큐의 우선순위로 올 수 있게 설정해주었다.