[Java] BOJ 16948 데스 나이트

16948번: 데스 나이트

---

정답 코드

• 문제에서 주어진 6방향으로만 이동 가능
• BFS로 해당 시작점 - 도착점 이동 거리 출력

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static int[] dr = { -2, -2, 0, 0, 2, 2 };
    static int[] dc = { -1, 1, -2, 2, -1, 1 };
    static int N, cnt;
    static int[] p1, p2;
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        visit = new boolean[N][N];

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

        p1 = new int[] { r1, c1 };
        p2 = new int[] { r2, c2 };

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

    private static int BFS() {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(p1);
        visit[p1[0]][p1[1]] = true;

        while (!queue.isEmpty()) {
            int qSize = queue.size();
            cnt++;
            for (int i = 0; i < qSize; i++) {
                int[] now = queue.poll();
                if (now[0] == p2[0] && now[1] == p2[1]) {
                    return cnt - 1;
                }

                for (int dic = 0; dic < 6; dic++) {
                    int nr = now[0] + dr[dic];
                    int nc = now[1] + dc[dic];

                    if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
                        continue;
                    }

                    if (!visit[nr][nc]) {
                        visit[nr][nc] = true;
                        queue.add(new int[] { nr, nc });
                    }
                }
            }
        }
        return -1;
    }
}