[백준 18404] 현명한 나이트 -JAVA // le_effort//

현명한 나이트

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	82	53	41	65.079%

문제

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

xxxxxxxxxx
5 3
2 4
3 2
3 5
4 5

예제 출력 1

1 2 1

 

풀이

사용 알고리즘 : bfs

 

쉬운 문제라 풀이가 간단하다.

map 전체에 걸리는 횟수를 체크하고 목표 좌표를 출력하면 끝.

 

 

 

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,m,x,y;
    static int knight_x,knight_y;
    static int map[][];
    static boolean visited[][];
    static int dx[]= {-2,-2,-1,-1,1,1,2,2};
    static int dy[]= {-1,1,-2,2,-2,2,-1,1};
    static int cnt =0;
    static ArrayList<Node> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    static Queue<Node>q = new LinkedList<>();
    public static void main(String[] args)  throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        visited = new boolean[n+1][n+1];
        
        map = new int[n+1][n+1];
        
        String[] tt= br.readLine().split(" ");
        knight_x = Integer.parseInt(tt[0]);
        knight_y = Integer.parseInt(tt[1]);
        q.add(new Node(knight_x,knight_y,0));
        visited[knight_x][knight_y]=true;
        
        for(int i=0; i<m; i++) {
            String[] input = br.readLine().split(" ");  
            x = Integer.parseInt(input[0]);
            y = Integer.parseInt(input[1]);
            list.add(new Node(x,y,0));
        }
        
    
        bfs();
        
        for(int i=0; i<list.size(); i++) {
            Node a = list.get(i);
            sb.append(map[a.x][a.y]+" ");
        }
        System.out.println(sb);
    }
    public static void bfs() {
        while(!q.isEmpty()) {
            Node a=  q.poll();
            for(int i=0; i<8; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(nx>=1 && ny>=1 && nx<=n && ny<=n) {
                    if(!visited[nx][ny]) {
                        map[nx][ny]=a.time+1;
                        visited[nx][ny]=true;
                        q.add(new Node(nx,ny,a.time+1));
                    }
                }
            }
        }
    }
}
class Node{
    int x,y,time;
    Node(int x, int y, int time){
        this.x=x;
        this.y=y;
        this.time=time;
    }
}