7565 나이트의 이동 (JAVA)

• Queue에 x,y 좌표를 삽입하기 위해, Point 클래스를 만들어 사용했다.
• 다른 정점으로 이동할때, x와 y가 각각 1혹은 2씩 증가 감소하는 문제이다.
• dx, dy 배열의 값만 수정한다면 전형적인 BFS 최단거리 문제와 같다.

public class Main {

    static class Point{
        int hei;
        int wid;
        public Point(int hei, int wid) {
            this.hei = hei;
            this.wid = wid;
        }
    }

    static int m;
    static boolean[][] ch;
    
    // 말이 움직이는 거리
    static int[] dx = {-2,-1,1,2,2,1,-1,-2};
    static int[] dy = {1,2,2,1,-1,-2,-2,-1};

    static int bfs(int s_x,int s_y,int e_x,int e_y){
        int L = 0;
        Queue<Point> q = new LinkedList<>();
        ch[s_y][s_x] = true;
        q.offer(new Point(s_y, s_x));
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0; i<len; ++i){
                Point v = q.poll();
                
                // 현재 위치가 목표점과 같다면 BFS를 종료하고, 탐색한 레벨을 반환
                if(v.wid == e_x && v.hei == e_y)
                    return L;
                for(int j=0; j<dx.length; ++j){
                    int nv_x = v.wid + dx[j];
                    int nv_y = v.hei + dy[j];
                    if(nv_x >= 0 && nv_y >= 0
                        && nv_x < m && nv_y < m
                        && !ch[nv_y][nv_x]){
                        ch[nv_y][nv_x] = true;
                        q.offer(new Point(nv_y, nv_x));
                    }
                }
            }
            L++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while(n-->0) {
            m = sc.nextInt();
            ch = new boolean[m][m];
            int s_x = sc.nextInt();
            int s_y = sc.nextInt();
            int e_x = sc.nextInt();
            int e_y = sc.nextInt();

            System.out.println(bfs(s_x, s_y, e_x, e_y));
        }
    }
}