7562번: 나이트의 이동

Joo·2022년 11월 14일

그래프 탐색 백준

백준

목록 보기

14/113

https://www.acmicpc.net/problem/7562

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다.

체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는

나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

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

예제 입력 1

예제 출력 1

5
28
0

+) 예제 입력 2

+) 예제 출력 2

+) 예제 입력 3

+) 예제 출력 3

0
0

+) 예제 입력 4

+) 예제 출력 4

풀이

💡 목적지로 가는 `최단거리`를 구하는 문제 → DFS가 아닌 BFS로 풀어야 함!!

글 읽기 - 최단거리에 DFS보다 BFS를 사용하는 이유는 무엇인가요?

[그래프] 27. BFS로 찾은 경로가 최단 경로인 이유

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 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();
    public static final int NUMBER_OF_DIRECTION = 8;
    private static int testCase;
    private static int sizeOfChessboard;
    private static Point start;
    private static Point destination;
    private static boolean[][] visited;
    private static int[][] direction = {
            {2, 1}, {2, -1},    // 오른쪽 x+2
            {-2, 1}, {-2, -1},  // 왼쪽 x-2
            {-1, -2}, {1, -2},   // 위 y-2
            {-1, 2}, {1, 2}    // 아래 y+2
    };

    static class Point {
        private int x;
        private int y;
        private int count;

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

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        testCase = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCase; i++) {
            input();
            process();
        }

        output();
    }

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        sizeOfChessboard = Integer.parseInt(st.nextToken());
        visited = new boolean[sizeOfChessboard][sizeOfChessboard];

        st = new StringTokenizer(br.readLine());
        start = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

        st = new StringTokenizer(br.readLine());
        destination = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
    }

    private static void process() {
        bfs(start);
        sb.append(destination.getCount()).append("\n");
    }

    private static void bfs(Point start) {
        Queue<Point> queue = new LinkedList<>();

        queue.add(start);
        visited[start.getX()][start.getY()] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int x = point.getX();
            int y = point.getY();
            int count = point.getCount();
            int newX;
            int newY;

            for (int i = 0; i < NUMBER_OF_DIRECTION; i++) {
                newX = x + direction[i][0];
                newY = y + direction[i][1];

                if (newX < 0 || newY < 0 || newX >= sizeOfChessboard || newY >= sizeOfChessboard) {
                    continue;
                }

                if (visited[newX][newY]) {
                    continue;
                }

                if (newX == destination.getX() && newY == destination.getY()) {
                    destination.setCount(count + 1);

                    return;
                }

                //count++;

                //queue.add(new Point(newX, newY, count));
                queue.add(new Point(newX, newY, count + 1));
                visited[newX][newY] = true;

                //count--;
            }
        }
    }

    private static void output() {
        System.out.print(sb);
    }

}