[백준] 16948번 : 데스 나이트 Silver1(실버1) - JAVA[자바]

[Silver I] 데스 나이트 - 16948

문제 링크

성능 요약

메모리: 13680 KB, 시간: 128 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2023년 11월 17일 09:25:11

문제 설명

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r₁, c₁), (r₂, c₂)가 주어진다. 데스 나이트가 (r₁, c₁)에서 (r₂, c₂)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r₁, c₁, r₂, c₂가 주어진다.

출력

첫째 줄에 데스 나이트가 (r₁, c₁)에서 (r₂, c₂)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Main {
    static int n;
    static int[][] map;
    static int[] dirX = {-2,-2,0,0,2,2};
    static int[] dirY = {-1,1,-2,2,-1,1};
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new int[n][n];
        int startX = sc.nextInt();
        int startY = sc.nextInt();
        int endX = sc.nextInt();
        int endY = sc.nextInt();

        bfs(startX,startY,endX,endY);
        System.out.println(map[endX][endY] ==  0? -1 : map[endX][endY]);
    }

    private static void bfs(int startX, int startY, int endX,int endY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startX,startY});

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];

            for(int i = 0; i < dirX.length; i++){
                int nextX = curX + dirX[i];
                int nextY = curY + dirY[i];
                if(nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map[nextX].length){
                    continue;
                }
                if(nextX == startX && nextY == startY){
                    continue;
                }
                if((map[nextX][nextY] == 0) || (map[nextX][nextY] > map[curX][curY] + 1)){
                    map[nextX][nextY] = map[curX][curY] + 1;
                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }
    }
}