백준 16948: 데스 나이트 [Java] - 포포

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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을 출력한다.

 

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

---

내 제출

public class No16948 {
    static int[] dx = {-2, -2, 0, 0, 2, 2};
    static int[] dy = {-1, 1, -2, 2, -1, 1};
    static int n;
    static Queue<Point> qu;
    static int[][] arr;
    static boolean[][] visit;
    static int count;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        arr = new int[n][n];
        visit = new boolean[n][n];
        qu = new LinkedList<>();

        int x = Integer.parseInt(st.nextToken(" "));
        int y = Integer.parseInt(st.nextToken(" "));

        Point start = new Point(x, y);  // 출발지

        x = Integer.parseInt(st.nextToken(" "));
        y = Integer.parseInt(st.nextToken(" "));
        
        Point fin = new Point(x, y);  // 도착지
        count = 0;

        bfs(start, fin);
        System.out.println(arr[fin.x][fin.y]);
    }

    private static void bfs(Point start, Point fin) {
        qu.offer(start);
        visit[start.x][start.y]= true;

        while (!qu.isEmpty()) {
            Point p = qu.poll();

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

                if(nx <0 || ny<0 || nx>=n || ny>=n) continue;

                if(!visit[nx][ny]){
                    qu.offer(new Point(nx, ny));
                    visit[nx][ny] = true;
                    arr[nx][ny] = arr[p.x][p.y] + 1;
                }

                if(nx == fin.x && ny == fin.y){

                    return;
                }
            }
        }
        //도착하지 못하고 큐가 비어버리면 -1를 출력하고 종료한다.
        System.out.println(-1);
        System.exit(0);
    }

    static class Point{
        int x;
        int y;

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

출발지, 도착지 좌표를 각각 start, fin에 저장한 뒤
bfs로 해결했다. 도착지에 다다르지 못하고 큐가 비어버린 경우에는 -1를 출력하고 종료하였다.