[백준 16748번] 데스 나이트

문제

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

---

정답

간단하게 깊이 우선 탐색으로 풀면 된다.

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

public class Main {
    static int[][] map;
    static boolean [][] visited;
    static int[] dx = {-2,-2,0,0,2,2};
    static int[] dy = {-1,1,-2,2,-1,1};
    static class RC{
        int r,c;
        public RC(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());    //체스판 크기
        map = new int[n][n];
        visited = new boolean[n][n];

        String[] XY = br.readLine().split(" ");
        int r1 = Integer.parseInt(XY[0]);
        int c1 = Integer.parseInt(XY[1]);
        int r2 = Integer.parseInt(XY[2]);
        int c2 = Integer.parseInt(XY[3]);

        Queue<RC> que = new LinkedList<RC>();
        que.add(new RC(r1,c1));
        map[r1][c1] = 0;
        visited[r1][c1] = true;
        boolean can = false;

        while(!que.isEmpty()) {
            RC now = que.poll();
            //지금 방문한 칸이 목표 칸이면 break;
            if(now.r == r2 && now.c == c2) {
                can = true;
                break;
            }
            visited[now.r][now.c] = true;
            //이동할수 있는 칸 탐색
            for(int i=0;i<6;i++) {
                int nr = now.r + dx[i];
                int nc = now.c + dy[i];
                //범위 밖이면 무시
                if(nr >=n || nc >=n || nr <0 || nc<0) continue;
                //범위 안이면 방문했는지 아닌지 판단
                if(visited[nr][nc]) continue;
                //방문 안했으면 체크
                visited[nr][nc] = true;
                map[nr][nc] = map[now.r][now.c]+1;
                que.add(new RC(nr,nc));
            }
        }
        if(can) {
            System.out.println(map[r2][c2]);
        }else {
            System.out.println("-1");
        }
        br.close();
    }
}