18404번: 현명한 나이트

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

문제

`NxN 크기 체스판의 특정한 위치에 하나의 나이트`가 존재한다.

이때 `M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산하는 프로그램`을 작성하시오.

나이트는 일반적인 체스(Chess)에서와 동일하게 이동할 수 있다.

현재 나이트의 위치를 (X,Y)라고 할 때, 나이트는 다음의 8가지의 위치 중에서 하나의 위치로 이동한다.

(X-2,Y-1), (X-2,Y+1), (X-1,Y-2), (X-1,Y+2), (X+1,Y-2), (X+1,Y+2), (X+2,Y-1), (X+2,Y+1)

N=5일 때, 나이트가 (3,3)의 위치에 존재한다면 이동 가능한 위치는 다음과 같다. 나이트가 존재하는 위치는 K, 이동 가능한 위치는 노란색으로 표현하였다.

예를 들어 N=5, M=3이고, 나이트가 (2,4)의 위치에 존재한다고 가정하자. 또한 상대편 말의 위치가 차례대로 (3,2), (3,5), (4,5)라고 하자. 이때 각 상대편 말을 잡기 위한 최소 이동 수를 계산해보자. 아래 그림에서는 상대편 말의 위치를 E로 표현하였다. 단, 본 문제에서 위치 값을 나타낼 때는 (행,열)의 형태로 표현한다.

각 상대편 말을 잡기 위한 최소 이동 수는 차례대로 1, 2, 1이 된다.

입력

첫째 줄에 `N과 M`이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000)

둘째 줄에 나이트의 위치 (*X*, *Y*)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ X, Y ≤ N)

셋째 줄부터 *M*개의 줄에 걸쳐 각 상대편 말의 위치 (*A*, *B*)를 의미하는 A와 B가 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ A, B ≤ N)

단, 입력으로 주어지는 모든 말들의 위치는 중복되지 않으며, 나이트가 도달할 수 있는 위치로만 주어진다.

출력

첫째 줄에 각 상대편 말을 잡기 위한 최소 이동 수를 공백을 기준으로 구분하여 출력한다.

단, 출력할 때는 입력 시에 상대편 말 정보가 주어졌던 순서에 맞게 차례대로 출력한다.

예제 입력 1

5 3
2 4
3 2
3 5
4 5

예제 출력 1

1 2 1

풀이

package graph_search;

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 Main_18404 {

    private static final int COUNT_OF_DIRECTION = 8;
    private static int sizeOfChessboard;
    private static int countOfPiece;
    private static Piece[] pieces;
    private static boolean[][] visited;
    private static Piece queen;
    private static int[][] direction = {
            {2, 1}, {2, -1},    // 오른쪽 x+2
            {-2, 1}, {-2, -1},  // 왼쪽 x-2
            {-1, -2}, {1, -2},   // 위 y-2
            {-1, 2}, {1, 2}    // 아래 y+2
    };
    private static int[] result;

    static class Piece {
        int x;
        int y;
        int count;

        public Piece(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        sizeOfChessboard = Integer.parseInt(st.nextToken());
        countOfPiece = Integer.parseInt(st.nextToken());

        visited = new boolean[sizeOfChessboard + 1][sizeOfChessboard + 1];
        pieces = new Piece[countOfPiece + 1];
        result = new int[countOfPiece + 1];

        st = new StringTokenizer(br.readLine());
        queen = new Piece(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

        for (int i = 1; i <= countOfPiece; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            pieces[i] = new Piece(x, y, 0);
        }

    }

    private static void process() {
        bfs();
    }

    private static void bfs() {
        Queue<Piece> queue = new LinkedList<>();
        int newX;
        int newY;

        queue.add(queen);
        visited[queen.getX()][queen.getY()] = true;

        while (!queue.isEmpty()) {
            Piece piece = queue.poll();
            int x = piece.getX();
            int y = piece.getY();
            int count = piece.getCount();

            for (int i = 0; i < COUNT_OF_DIRECTION; i++) {
                newX = x + direction[i][0];
                newY = y + direction[i][1];

                if (newX < 0 || newY < 0 || newX > sizeOfChessboard || newY > sizeOfChessboard) {
                    continue;
                }

                if (visited[newX][newY]) {
                    continue;
                }

                if (getTargetNumber(newX, newY) != -1) {
                    result[getTargetNumber(newX, newY)] = count + 1;
                }

                queue.add(new Piece(newX, newY, count + 1));
                visited[newX][newY] = true;
            }
        }
    }

    private static int getTargetNumber(int newX, int newY) {
        for (int i = 1; i <= countOfPiece; i++) {
            if (newX == pieces[i].getX() && newY == pieces[i].getY()) {
                return i;
            }
        }

        return -1;
    }

    private static void output() {
        for (int i = 1; i <= countOfPiece; i++) {
            System.out.print(result[i] + " ");
        }
    }

}