[백준 | Java] 7562 나이트의 이동

내 풀이

나이트가 최소 몇 번만에 이동하는지를 구하는 문제이므로 최단거리를 구할 때 사용하는 알고리즘인 BFS를 사용했다.

이 문제와 백준 2178번 미로 탐색과 비슷해 2178번을 이해하고 있다면 쉽게 풀었을 문제이다.
👉 백준 2178 미로 탐색 풀이

우선, 나이트가 한 번에 이동할 수 있는 거리 상수는 다음과 같이 그래프에서 총 8개로 정의할 수 있다.

두꺼운 펜으로 쓴 각각의 번호가 x축 방향과 y축 방향을 그래프에서의 이동 거리를 표현한 것으로 이해하면 된다.

현 위치의 노드에서 인접 노드의 위치를 구할 때 사용될 상수배열이므로 각 배열 번호의 짝은 달라지면 안된다.
사용 예시는 다음과 같다.

for (int i = 0; i < 8; i++) {
	int nx = xy[0] + dx[i];
    int ny = xy[1] + dy[i];
}

구현 과정은 다음과 같다.

1. 보드판 위에서 나이트의 현 위치의 값만 1로 설정
2. BFS 연산 수행
   a. 상하좌우를 탐색해 보드판 내에 있는 위치이고, 방문하지 않은 위치이면 큐에 삽입,방문 표시, 거리 삽입
   b. 큐가 빌 때 까지 다시 상하좌우 탐색 반복
3. 목표 위치의 거리값 반환
   (0부터 입력받았으므로 목표 위치의 거리값 - 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 {
    static int I;
    static int[] n;  // 현재 있는 칸
    static int[] w;  // 이동하려고 하는 칸
    static int[][] board;
    static int[] dx = {1, -1, 1, -1, 2, 2, -2, -2};
    static int[] dy = {2, 2, -2, -2, 1, -1, 1, -1};

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

        int cnt = Integer.parseInt(br.readLine());
        n = new int[2];
        w = new int[2];

        for (int i = 0; i < cnt; i++) {
            I = Integer.parseInt(br.readLine());
            board = new int[I][I];

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                n[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                w[j] = Integer.parseInt(st.nextToken());
            }

            board[n[0]][n[1]] = 1;
            bfs();
            int result = board[w[0]][w[1]];
            sb.append(result - 1).append('\n');
        }
        System.out.println(sb);
    }

    static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[I][I];

        queue.add(new int[] {n[0], n[1]});
        visited[n[0]][n[1]] = true;

        while (!queue.isEmpty()) {
            int[] xy = queue.poll();
            for (int i = 0; i < 8; i++) {
                int nx = xy[0] + dx[i];
                int ny = xy[1] + dy[i];

                if (nx < I && nx >= 0 && ny < I && ny >= 0 && !visited[nx][ny]) {
                    queue.add(new int[] {nx, ny});
                    visited[nx][ny] = true;
                    board[nx][ny] = board[xy[0]][xy[1]]+1;
                }
            }
        }

    }
}