백준 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

 

• 풀이

 

https://hoshi03.tistory.com/272

백준 7565 : 나이트의 이동

이 문제와 거의 똑같은 문제

처음에는 상대 말이 들어올때마다 visit이랑 dist를 초기화해야 되는 건가 생각했는데 어차피 bfs는 처음에 받은

나이트 위치 기준으로 한번만 돌고 상대 말 들은 dist만 출력하면 되는 코드였다

import java.util.*;
import java.io.*;

public class Main{

    static int N, M;
    static int[][] board;
    static int[][] dist;
    static boolean[][] visit;
    static int[][] dir = {{2,1}, {1,2}, {-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

    static void bfs(int x, int y){
        Queue<Integer> q = new LinkedList<>();
        visit[x][y] = true;
        q.add(x);
        q.add(y);
        while (!q.isEmpty()){
            x = q.poll();
            y = q.poll();
            for (int i = 0; i < 8; i++){
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
                if (visit[nx][ny]) continue;
                q.add(nx);
                q.add(ny);
                visit[nx][ny] = true;
                dist[nx][ny] = dist[x][y]+1;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        board = new int[N+1][N+1];
        dist = new int[N+1][N+1];
        visit = new boolean[N+1][N+1];

        int startX = in.nextInt();
        int startY = in.nextInt();
        bfs(startX, startY);

        while (M-- > 0){
            int targetX = in.nextInt();
            int targetY = in.nextInt();
            System.out.print(dist[targetX][targetY] + " ");
        }
    }
}