[항해99 취업 리부트 코스 학습일지] 알고리즘 문제풀이

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

문제

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

---

입력

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

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

---

출력

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

---

풀이

전형적인 BFS 문제이다.
보통 상하좌우로 탐색하는 문제가 많은데 이 문제는 8방향을 탐색해야 한다.
테스트 케이스마다 BFS를 사용해 탐색한다.

좌표 정보를 저장할 Coordinate객체를 생성하고 큐에 넣어서 탐색한다.

이동 횟수를 기록할 체스판 배열을 생성하고
8방향을 돌며 이동 횟수를 기록한다.
방문 여부는 이동 횟수를 기준으로 판단한다.

정수형 배열 기본값이 0이니, 해당 좌표의 이동 횟수가 0일 때만 큐에 삽입한다.
현재 있는 칸은 0으로 방문 기록이 안되니 현재 있는 칸의 이동 횟수를 1로 초기화한다.

방문 기록을 하는 boolean타입의 배열을 따로 만들어주지 않고 조건문을 더 간단히 하려고 이렇게 작성했다.

방문 기록을 1부터 했으니 반환할 때 1을 빼고 반환한다.

전체 코드

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 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int targetX = Integer.parseInt(st.nextToken());
            int targetY = Integer.parseInt(st.nextToken());

            sb.append(bfs(n, startX, startY, targetX, targetY)).append('\n');
        }

        System.out.println(sb);
    }

    private static final int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1};
    private static final int[] dy = {2, 1, -1, -2, -2, -1, 1, 2};

    private static int bfs(int n, int startX, int startY, int targetX, int targetY) {
        Queue<Coordinate> q = new LinkedList<>();
        // 시작 좌표 삽입
        q.add(new Coordinate(startX, startY));

        // 이동 횟수 기록
        int[][] board = new int[n][n];
        // 처음 좌표 1로 초기화
        board[startX][startY] = 1;

        while (!q.isEmpty()) {
            Coordinate coordinate = q.poll();
            int x = coordinate.x;
            int y = coordinate.y;

            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 범위 조건
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    // 이동 횟수가 아직 기록되지 않은 좌표라면 큐에 삽입
                    if (board[nx][ny] == 0) {
                        q.add(new Coordinate(nx, ny));
                        // 이동 횟수 기록
                        board[nx][ny] = board[x][y] + 1;
                    }
                }
            }
        }

        // 횟수 1부터 시작했으니 1 빼고 반환
        return board[targetX][targetY] - 1;
    }

    static class Coordinate {
        private final int x;
        private final int y;

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

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.