[JAVA] 백준 7562번: 나이트의 이동 ( 초급 2-43 )

문제

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

입력

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

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

출력

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

 

문제 풀이

전형적인 bfs 문제라고 볼 수 있다.

체스 시작 지점으로 부터 종료 지점까지 가는데 까지 걸리는 최단 거리 턴을 구하는 문제이다.

 

시작 지점과 종료 지점이 같을 경우 결과 값에 0을 저장하고

다를 경우 시작 지점으로 부터 종료 지점 까지 bfs를 이용하여 최단거리를 구하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon7562_2 {
    private static int[] rowTemp = { -2, -2, -1, -1, 1, 1, 2, 2 };
    private static int[] colTemp = { -1, 1, -2, 2, -2, 2, -1, 1 };
    private static int size;
    private static boolean[][] visit;
    private static int[][] distInfo;
    private static int endRow;
    private static int endCol;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 체스 게임 진행
        for (int i = 0; i < n; i++) {
            size = Integer.parseInt(br.readLine());
            distInfo = new int[size][size];
            visit = new boolean[size][size];

            StringTokenizer st = new StringTokenizer(br.readLine());
            int startRow = Integer.parseInt(st.nextToken());
            int startCol = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            endRow = Integer.parseInt(st.nextToken());
            endCol = Integer.parseInt(st.nextToken());

            Queue<Position7562> queue = new LinkedList<>();
            visit[startRow][startCol] = true;
            // 시작 지점과 종료 지점이 똑같을 경우 0을 저장
            if (startRow == endRow && startCol == endCol) {
                sb.append(0 + "\n");
            } else {
                // 시작 지점과 종료 지점이 다를 경우 시작 지점으로 부터 BFS를 진행한다.
                queue.add(new Position7562(startRow, startCol));
                bfs7562(queue);
            }
        }

        System.out.println(sb);
    }

    private static void bfs7562(Queue<Position7562> queue) {
        while (!queue.isEmpty()) {
            Position7562 position7562 = queue.remove();
            int row = position7562.row;
            int col = position7562.col;

            for (int i = 0; i < 8; i++) {
                int nextRow = row + rowTemp[i];
                int nextCol = col + colTemp[i];
                if (nextRow >= 0 && nextCol >= 0 && nextRow < size && nextCol < size) {
                    if (!visit[nextRow][nextCol]) {
                        if (nextRow == endRow && nextCol == endCol) {
                            sb.append(distInfo[row][col] + 1 + "\n");
                            return;
                        }
                        visit[nextRow][nextCol] = true;
                        distInfo[nextRow][nextCol] = distInfo[row][col] + 1;
                        queue.add(new Position7562(nextRow, nextCol));
                    }
                }
            }

        }
    }
}

class Position7562 {
    int row;
    int col;

    Position7562(int row, int col) {
        this.row = row;
        this.col = col;
    }
}