[백준] 7562 나이트의 이동 자바(Java)

문제설명

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

 

입력

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

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

 

출력

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

 

풀이

처음에는 문제가 이해되지 않아 여러 번 반복해서 본 거 같다. 문제의 사진 처럼 4,4를 기준으로 각 8방향에 대해 시작점부터 끝지점까지 가는 최소의 카운트를 출력하면 되기 때문에 BFS로 풀이하였다. 다만 Point 함수를 선언하면서 x, y뿐만 아니라 카운트도 함께 선언하여 최소 카운트를 출력하도록 하였다. 이런 유형의 문제를 만날 때 어떻게 구현할지에 대해 고민을 많이 하게 되는 것 같아서 관련 문제를 많이 풀이해야 겠다는 생각이 들었다...

 

통과한 코드 ✅

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

public class Main {
    public static int T, n;
    public static int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
    public static int dy[] = {-2, 2, 2, -2, 1, -1, 1, -1};

    public static class Point {
        int x;
        int y;
        int cnt;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Point(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }

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

        T = Integer.parseInt(st.nextToken());

        while (T-- > 0) {
            n = Integer.parseInt(br.readLine());
            Point[] points = new Point[2]; // 시작점, 끝점을 저장

            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken()); // 각 시작점의 x
                int y = Integer.parseInt(st.nextToken()); // 각 끝점의 y

                points[i] = new Point(x, y);
            }
            System.out.println(dfs(points));
        }
    }


    public static int dfs(Point points[]) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(points[0]); // 시작점을 큐에 삽입

        boolean visited[][] = new boolean[n][n]; // 방문 배열 선언
        visited[points[0].x][points[0].y] = true; // 현재 시작점 방문처리

        while (!queue.isEmpty()) {
            Point p = queue.poll(); // 시작점부터

            if (p.x == points[1].x && p.y == points[1].y) { // 현재 점과 끝점과 같다면 카운트를 반환하고 종료
                return p.cnt;
            }
            for (int i = 0; i < 8; i++) {
                int cx = p.x + dx[i]; // 각 대각선 방향을 돌아가며 구함
                int cy = p.y + dy[i];

                if (cx >= 0 && cy >= 0 && cx < n && cy < n) {
                    if (!visited[cx][cy]) {
                        visited[cx][cy] = true; // 방문하지 않았다면 true
                        queue.offer(new Point(cx, cy, p.cnt + 1)); // 카운트 증가
                    }
                }
            }
        }
        return -1;
    }
}