백준 7562번 - 나이트의 이동

백준 - 나이트

코드

public class Main {

    static int[] arrx = {2,2,-2,-2,1,1,-1,-1};
    static int[] arry = {1,-1,1,-1,2,-2,2,-2};

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

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

            int n = sc.nextInt();
            int sx = sc.nextInt();
            int sy = sc.nextInt();
            int ex = sc.nextInt();
            int ey = sc.nextInt();

            int[][] map = new int[n][n];
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{sx,sy});

            while (!queue.isEmpty()) {
                int[] current = queue.poll();

                int cx = current[0];
                int cy = current[1];

                if (cx == ex && cy == ey) {
                    System.out.println(map[cy][cx]);
                    break;
                }

                for (int j = 0; j < arrx.length; j++) {
                    int nx = arrx[j] + cx;
                    int ny = arry[j] + cy;

                    if (  ny>=0 && ny<n  && nx>=0 && nx<n && map[ny][nx] ==0 ) {
                        queue.offer(new int[]{nx,ny});
                        map[ny][nx] += map[cy][cx]+1;
                    }
                }
            }
        }
    }
}

풀이

체스의 나이트가 이동을 하는데 목적지까지 얼마나 빠르게 도착할 수 있는지를 계산해야 하는 문제로 미리 나이트가 이동할 수 있는 경로를 arrx,arry에 저장한다. queue에 시작 위치를 넣고 bfs로 푸는데 if문을 통해 목적지와 같은 값이라면 값을 출력하고 종료하며 아니라면 queue에는 지나가지 않은 경로의 경우 값을 넣으며 이 때 해당 칸은 경로+1을 해준다.

출처 : 백준 - 나이트의 이동