[JAVA] 백준 7562번- 나이트의 이동

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

7562번: 나이트의 이동

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

    static class Point {
        int x, y;

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

    static Queue<Point> q = new LinkedList<>();

    public static void bfs(int x, int y) {
        q.add(new Point(x, y));

        while (!q.isEmpty()) {
            Point p = q.poll();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= n || arr[nx][ny] != -1) continue; 

                // 방문하지 않았을 경우에 
                arr[nx][ny] = arr[p.x][p.y] + 1; // 거리 증가
                q.add(new Point(nx, ny));

            }
        }
    }

    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();

        while (T-- > 0) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n][n];

            for(int x[] : arr){
                Arrays.fill(x, -1);
            }
            StringTokenizer st;
            st = new StringTokenizer(br.readLine());
            int now_x = Integer.parseInt(st.nextToken());
            int now_y = Integer.parseInt(st.nextToken());

            arr[now_x][now_y] = 0; // 방문 처리
            bfs(now_x, now_y);

            st = new StringTokenizer(br.readLine());
            int next_x = Integer.parseInt(st.nextToken());
            int next_y = Integer.parseInt(st.nextToken());

            sb.append(arr[next_x][next_y] + "\n");
        }
        System.out.println(sb);
    }
}

 

 

입력받은 arr를 -1로 초기화 시키고, 처음 시작점을 0으로 초기화 한다음 bfs로 탐색하며 방문한 곳을 1씩 증가시켜 거리를 기록해나간다.