백준 7562번 나이트의 이동 자바 풀이

❓문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

---

🔠 입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

---

🖨️출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

---

✍️ 예제 입력

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

✔️ 예제 출력

5
28
0

 

---

💡해설

하다가 잘 안되서 좀 검색해봤다.-ㅅ -

나이트의 이동방향이 8방향이기 때문에 좌표를 설정해둬야 한다.

좌표를 잘 설정하면 bfs로 (빠른 길 탐색이기 때문에) 좌표를 움직여가면서 길을 찾으면 된다.

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

public class Main {

    static int[] dx = { -2, -1, -2, -1, 1, 2, 2, 1 };
    static int[] dy = { -1, -2, 1, 2, 2, 1, -1, -2 };
    static Point end;
    static int n, l;
    static boolean[][] visited;
    static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            l = Integer.parseInt(br.readLine());
            visited = new boolean[l][l];

            Point start = new Point(0, 0, 0);
            String input = br.readLine();
            start.r = Integer.parseInt(input.split(" ")[0]);
            start.c = Integer.parseInt(input.split(" ")[1]);

            end = new Point(0, 0, 0);
            input = br.readLine();
            end.r = Integer.parseInt(input.split(" ")[0]);
            end.c = Integer.parseInt(input.split(" ")[1]);

            bfs(start);
        }

        result.stream().forEach(System.out::println);

    }

    private static void bfs(Point point) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(point);
        visited[point.r][point.c] = true;

        while (!queue.isEmpty()) {
            Point temp = queue.poll();
            int r = temp.r;
            int c = temp.c;
            int cnt = temp.cnt;

            if (r == end.r && c == end.c) {
                result.add(cnt);
                return;
            }

            for (int i = 0; i < 8; i++) {
                int nr = r + dx[i];
                int nc = c + dy[i];

                if (nr > -1 && nc > -1 && nc < l && nr < l && !visited[nr][nc]) {
                    queue.add(new Point(nr, nc, cnt + 1));
                    visited[nr][nc] = true;
                }
            }
        }
    }

    public static class Point {
        int r;
        int c;
        int cnt;

        public Point(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }

}