[백준] 16948번 : 데스 나이트

16948번: 데스 나이트

---

[BFS]

최소 이동 횟수를 찾는 문제는 DFS보다 BFS가 확실하다. BFS는 모든 방향으로 한 칸씩 나아가지만, DFS는 한 방향으로 끝을 볼 때 까지 나아가기 때문이다.

 

BFS를 이용해 N x N 맵이 있다고 가정하고 탐색할 수 있는 맵을 모두 탐색할 때 까지 도착점에 도달하지 못하면 -1을 반환한다.

# Code </>

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

public class Main {

    static class Point{
        int y, x, m;
        public Point(int yy, int xx, int move){
            y=yy;
            x=xx;
            m=move;
        }
    }
    static int n;
    static int[] Y = {-2, -2, 0, 0, 2, 2}, X = {-1, 1, -2, 2, -1, 1};
    static boolean[][] visit = new boolean[200][200];

    static int BFS(int[] arr){
        Queue<Point> Q = new LinkedList<>();

        visit[arr[0]][arr[1]] = true;
        Q.add(new Point(arr[0], arr[1], 0));

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

            int y = p.y;
            int x = p.x;
            int m = p.m;

            if(y == arr[2] && x == arr[3]) return m;

            for(int a=0; a<6; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 0 || nx < 0 || ny > n-1 || nx > n-1 || visit[ny][nx]) continue;

                visit[ny][nx] = true;
                Q.add(new Point(ny, nx, m+1));
            }
        }
        return -1;
    }

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

        int[] loca = new int[4];
        for(int i=0; i<4; i++)
            loca[i] = Integer.parseInt(st.nextToken());

        System.out.println(BFS(loca));
    }
}