[백준]#16948 데스 나이트

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

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

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

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

예제 입력 1

7
6 6 0 12

예제 출력 1

4

예제 입력 2

6
5 1 0 5

예제 출력 2

-1

예제 입력 3

7
0 3 4 3

예제 출력 3

2

풀이

이 문제는 기본적인 BFS 알고리즘을 이용해서 푸는 문제로 문제를 보고 BFS를 이용하면 되겠다는 생각을 떠올린다면 쉽게 풀 수 있는 문제이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int[] dx = {-2, -2, 0, 0, 2, 2};
    static int[] dy = {-1, 1, -2, 2, -1, 1};
    static int N;
    static int target_r;
    static int target_c;
    static int min = -1;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        String[] input = br.readLine().split(" ");
        int r = Integer.parseInt(input[0]);
        int c = Integer.parseInt(input[1]);

        target_r = Integer.parseInt(input[2]);
        target_c = Integer.parseInt(input[3]);

        bfs(r, c);
        System.out.println(min);
    }

    public static void bfs(int r, int c) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        visited[r][c] = true;
        queue.add(new Pair(r, c, 0));

        while(!queue.isEmpty()) {
            Pair p = queue.poll();

            if(p.x==target_r && p.y==target_c) {
                min = p.cnt;
                return;
            }

            for(int i=0; i<6; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(nx>=0 && nx<N && ny>=0 && ny<N && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new Pair(nx, ny, p.cnt+1));
                }
            }

        }
    }

    public static class Pair {
        int x;
        int y;
        int cnt;

        public Pair(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}