[백준저지] 7562번 : 나이트의 이동

www.acmicpc.net/problem/7562

1. 문제

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

입)

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

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

출)

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

2. 풀이

import java.util.*;
public class Main {
	// 8 방향을 확인해야 함.
    static final int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    static final int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        // 테스트 케이스
        int t = sc.nextInt();
        while (t-- > 0) {
            // 체스판 크기
            int n = sc.nextInt();
            // 시작점 X
            int sx = sc.nextInt();
            // 시작점 Y
            int sy = sc.nextInt();
            // 목표점 X
            int ex = sc.nextInt();
            // 목표점 Y
            int ey = sc.nextInt();
            // 크기만큼 배열 생성
            int[][] d = new int[n][n];
            // -1로 초기화
            for (int i=0; i<n; i++) {
                Arrays.fill(d[i],-1);
            }
            Queue<Integer> q = new LinkedList<>();
            q.add(sx);
            q.add(sy);
            // 초기값 
            d[sx][sy] = 0;
            // 큐가 EMPTY될 때까지
            while (!q.isEmpty()) {
                int x = q.remove();
                int y = q.remove();
                // 8방향 확인하면서
                for (int k = 0; k < 8; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    	// 방문 안한 경우
                        if (d[nx][ny] == -1) {
                            d[nx][ny] = d[x][y] + 1;
                            q.add(nx);
                            q.add(ny);
                        }
                    }
                }
            }
            System.out.println(d[ex][ey]);
        }
    }
}

BFS 활용해서 처리함.