[백준] 16948번 데스 나이트(java)

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

16948번: 데스 나이트

핵심

bfs를 안다면 매우 쉽게 풀 수 있는 문제이다. 기존에 다루었던 네 방향에서 조금 응용된 느낌이다.

하지만 똑같은 방식으로 풀 수 있다.

 

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    static int[][] map;
    static int[][] result;
    static int[] dy = {-2,-2,0,0,2,2};
    static int[] dx = {-1,1,-2,2,-1,1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        map = new int[n][n];
        result = new int[n][n];
        int y = sc.nextInt();
        int x = sc.nextInt();

        bfs(y,x);

        System.out.println(result[sc.nextInt()][sc.nextInt()] -1);
    }
    public static void bfs(int y,int x){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y, x});
        result[y][x] = 1;

        while (!queue.isEmpty()){
            int[] move = queue.poll();

            for (int i =0; i< 6; i++){
                int moveY = move[0] + dy[i];
                int moveX = move[1] + dx[i];

                if (0<=moveY && moveY< result.length && 0<=moveX && moveX < result.length){
                    if (result[moveY][moveX] ==0){
                        result[moveY][moveX] = result[move[0]][move[1]]+1;
                        queue.add(new int[]{moveY, moveX});
                    }
                }
            }
        }
    }
}

 

해설

이전에 풀었던 문제들과 크게 다르지 않다. 이동범위가 달라졌으니,

그에 따라 이동 dy, dx를 알맞게 바꾸었다.

이후 시작점을 y, x로 받았다.

이제 bfs를 통해 값을 업데이트시켜 줬다.

첫 시작점을 1로 잡았기 때문에, 우리가 찾는 값에서 -1을 해줘야 한다.

이렇게 하면 좋은 점은 갈 수 없는 경우는 0으로 초기화되어 있기 때문에 자연스럽게 -1이 된다.

 

 

배운 점

이전에 풀었던 bfs들과 크게 다르지 않아 어려움 없었다.

첫 시작점을 1로 잡으니 코드가 더욱 깔끔해졌다.