[백준] 7562. 나이트의 이동

문제 링크

[백준] 7562. 나이트의 이동

풀이 과정

기본적인 BFS 탐색 문제로, 이동 가능한 방향이 체스의 나이트 이동 방향으로 조금 특이합니다. 문제에서 명시적으로 주어지진 않았지만, 무조건 이동이 가능하다는 전제 조건이 있는 것으로 보입니다.

static class Point {
    int x, y, cnt;

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

좌표까지의 이동 횟수를 기록하기 위해 따로 클래스를 하나 생성 후 객체를 만들며 문제를 풀었습니다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();

        for (int tc = 1; tc <= TC; tc++) {
            int l = sc.nextInt();
            boolean[][] visit = new boolean[l][l];
            Point start = new Point(sc.nextInt(), sc.nextInt(), 0);
            Point end = new Point(sc.nextInt(), sc.nextInt(), 0);

            int answer = 0;

            Queue<Point> queue = new LinkedList<>();
            visit[start.x][start.y] = true;
            queue.add(start);

            while (!queue.isEmpty()) {
                Point now = queue.poll();

                if (now.x == end.x && now.y == end.y) {
                    answer = now.cnt;
                    break;
                }

                for (int d = 0; d < 8; d++) {
                    int nx = now.x + dx[d], ny = now.y + dy[d];
                    if (nx < 0 || nx > l - 1 || ny < 0 || ny > l - 1 || visit[nx][ny]) continue;

                    visit[nx][ny] = true;
                    queue.add(new Point(nx, ny, now.cnt + 1));
                }
            }

            System.out.println(answer);
        }
    }

    static class Point {
        int x, y, cnt;

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