[백준] 7562번 : 나이트의 이동 - JAVA [자바]

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

bfs 알고리즘 문제이다.

1. 현재 위치에서 갈 수 있는 칸을 탐색한다. (문제의 말의 조건에 따라)
2. 아직 방문하지 않았으면 그 칸으로 이동하고 그 칸에 현재 칸의 숫자 + 1 을 대입한다. (1번 움직였기 때문에)
3. 1번과 2번을 반복하여 갈 수 있는 모든 체스판의 위치를 탐색했으면
4. 목표로 하는 칸의 숫자를 확인하고 그 칸의 숫자가 현재 입력받은 위치에서 목표로 하는 위치로 갈 때 말을 움직이는 횟수 즉, 답이다.

bfs 탐색을 하는 도중에 목표로 하는 x, y 값에 도달했으면 답을 출력하고 종료하면 더 최적화 할 수 있다.

추가로 좌표를 큐에 넣기 위해 spot 이라는 클래스를 정의했다.
문제에서 주어진 말이 갈 수 있는 칸의 위치의 배열

int[] xMove = {1, 2, 2, 1, -1, -2, -2, -1};
int[] yMove = {2, 1, -1, -2, 2, 1, -1, -2};

public class bj7562 {

    public static int N;
    public static int[][] chessboard;
    public static boolean[][] visited;
    static int[] xMove = {1, 2, 2, 1, -1, -2, -2, -1};
    static int[] yMove = {2, 1, -1, -2, 2, 1, -1, -2};

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

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

            N = Integer.parseInt(br.readLine());
            String line1 = br.readLine();
            String[] split = line1.split(" ");
            int currentX = Integer.parseInt(split[0]);
            int currentY = Integer.parseInt(split[1]);

            String line2 = br.readLine();
            String[] split1 = line2.split(" ");
            int destinationX = Integer.parseInt(split1[0]);
            int destinationY = Integer.parseInt(split1[1]);

            visited = new boolean[N][N];
            chessboard = new int[N][N];

            bfs(currentX, currentY);

            bw.write(chessboard[destinationX][destinationY] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs(int x, int y) {
        Queue<spot> queue = new LinkedList<>();
        queue.add(new spot(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            spot start = queue.poll();
            for (int i = 0; i < 8; i++) {
                int newX = start.x + xMove[i];
                int newY = start.y + yMove[i];

                if (newX >= 0 && newX < N) {
                    if (newY >= 0 && newY < N) {
                        // 탐색하는 칸이 땅이며 아직 방문하지 않은 곳이라면
                        if (!visited[newX][newY]) {
                            queue.add(new spot(newX, newY));
                            chessboard[newX][newY] = chessboard[start.x][start.y] + 1;
                            visited[newX][newY] = true;
                        }
                    }
                }
            }

        }
    }

    static class spot {
        int x;
        int y;

        spot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}