[BOJ] 16948번 데스 나이트 자바

문제

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

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을 출력한다.

풀이

#bfs

기본적인 bfs 문제.

최단 경로의 이동횟수를 찾아야 하므로 Node 의 cnt를 늘려가며 이동횟수를 찾는다.

코드

package BOJ.bfs;

import java.util.*;
import java.io.*;
public class No16948_데스나이트 {
    static int[] dx={-2,-2,0,0,2,2};
    static int[] dy={-1,1,-2,2,-1,1};
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        StringTokenizer st=new StringTokenizer(br.readLine());
        int r1=Integer.parseInt(st.nextToken());
        int c1=Integer.parseInt(st.nextToken());
        int r2=Integer.parseInt(st.nextToken());
        int c2=Integer.parseInt(st.nextToken());


        visited=new boolean[N][N];
        boolean flag=false;

        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(r1,c1,0));
        visited[r1][c1]=true;

        int cnt=0;
        l: while(!q.isEmpty()){
            Node cur=q.poll();
            int x=cur.x;
            int y=cur.y;

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

                if(nx<0||nx>=N||ny<0||ny>=N||visited[nx][ny]) continue;
                if(nx==r2&&ny==c2){
                    flag=true;
                    cnt=cur.cnt+1;
                    break l;
                }
                visited[nx][ny]=true;
                q.offer(new Node(nx,ny,cur.cnt+1));
            }
        }

        System.out.println(flag? cnt:-1);
    }

    static class Node {
        int x, y, cnt;
        public Node(int x, int y, int cnt){
            this.x=x;
            this.y=y;
            this.cnt=cnt;
        }
    }
}