[BOJ] 7562 나이트의 이동 (S1)

문제

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

풀이

이전에 풀었던 BFS 관련 문제들과 거의 유사하며 차이점으로는 방향이 8방향으로 변형된 형태이다.

도착지까지의 최소 이동 횟수를 구해야 하기 때문에 출발지에서 BFS 탐색을 하여 게임판 모든 좌표까지의 최소 이동 거리를 구한다.

이후에 출력할 때, 도착지의 좌표에 저장된 이동 횟수를 출력한다.

Code

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

public class Main {
    static int [][] board;
    static boolean [][] visited;
    static int count = 0;
    static int l, nowX, nowY, desX, desY;
    static Queue<int[]> queue;
    static int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int dy[] = {1, -1, 2, -2, 2, -2, 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 T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            l = Integer.parseInt(br.readLine());  // 체스판 한 변의 길이
            board = new int[l][l];
            visited = new boolean[l][l];
            
            // 나이트의 위치
            st = new StringTokenizer(br.readLine());
            nowX = Integer.parseInt(st.nextToken());
            nowY = Integer.parseInt(st.nextToken());
            
            // 도착지의 위치
            st = new StringTokenizer(br.readLine());
            desX = Integer.parseInt(st.nextToken());
            desY = Integer.parseInt(st.nextToken());
            
            bfs(nowX, nowY);
            
            // 게임판의 각 위치가 이동 횟수
            sb.append(board[desX][desY]).append("\n");
        }
        System.out.println(sb);
    }
    
    static void bfs(int x, int y) {
        queue = new ArrayDeque<>();
        queue.offer(new int [] {x, y});
        visited[x][y] = true;  // 방문 처리
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            
            for (int i = 0; i < 8; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                
                // 다음 좌표가 범위 내에 있고, 방문하지 않은 지점이라면
                if (nx >= 0 && ny >= 0 && nx < l && ny < l && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    board[nx][ny] = board[current[0]][current[1]] + 1;  // 이동 횟수를 증가시켜 저장
                    queue.offer(new int[] {nx, ny});
                }
            }
        }
    }
}