[JAVA] 백준 - 데스나이트 (BFS)

www.acmicpc.net/problem/16948

16948번: 데스 나이트

가장 기본적인 로직만 있는 문제.

 

상하좌우가 아니라 이동할 수 있는 다음 장소가 6군데라는점만 조심하면 된다.

 

또한 한번 방문한 곳을 또 방문하여 최단거리를 갱신하는 일은 없으므로 2차원 배열로 방문 체크를 해도된다.

 

import java.util.LinkedList;
import java.util.*;
class Main{

    static int n;
    static boolean[][] chess = new boolean[201][201];
    static int goalX,goalY;
    static int answer = Integer.MAX_VALUE;

    static int[] dx = {-2,-2,0,0,2,2};
    static int[] dy = {-1,1,-2,2,-1,1};

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        Pair start = new Pair(sc.nextInt(),sc.nextInt(),0);
        Queue<Pair> q = new LinkedList<>();
        q.add(start);
        chess[start.x][start.y] = true;
        goalX = sc.nextInt();
        goalY = sc.nextInt();

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

            if(p.x == goalX && p.y == goalY){
                if(answer > p.cnt){
                    answer = p.cnt;
                }
            }

            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) continue;

                if(chess[nx][ny]==false){
                    chess[nx][ny] = true;
                    q.add(new Pair(nx,ny,p.cnt+1));
                }
            }

        }

        System.out.println(answer==Integer.MAX_VALUE?-1:answer);

    }


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

}