나이트의 이동

📍 문제 설명

 

 

💡 접근

전형적인 BFS 문제

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, v, e, k, answer, cnt;
    static int[] arr;
    static long[] dp;
    static int[][] board;
    static boolean[][] visited;
    //static int[] dx = {-1,1,0,0};
    //static int[] dy = {0,0,-1,1};
    static int[] dx = {-2,-2,2,2,-1,-1,1,1};
    static int[] dy = {-1,1,-1,1,-2,2,-2,2};
    static ArrayList<Integer> list;
    static StringBuilder sb;
    static Queue<Point> q;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = kb.nextInt();
        for(int i = 0; i < tc; i++) {
            n = kb.nextInt(); // 체스판의 크기
            board = new int[n][n];
            visited = new boolean[n][n];
            int cx = kb.nextInt();
            int cy = kb.nextInt();
            int fx = kb.nextInt();
            int fy = kb.nextInt();

            answer = 0;

            T.solution(cx, cy, fx, fy);
        }

    }


    private void solution(int cx, int cy, int fx, int fy) {
        q = new LinkedList<>();
        q.offer(new Point(cx, cy));
        visited[cx][cy] = true;

        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                Point cp = q.poll();
                if (cp.x == fx && cp.y == fy) {
                    System.out.println(answer);
                    break;
                }
                for (int j = 0; j < 8; j++) {
                    int nx = cp.x + dx[j];
                    int ny = cp.y + dy[j];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) continue;

                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny));
                }
            }
            answer++;
        }

    }

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

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

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}