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

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

7562번: 나이트의 이동

 

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

class Node {
    int y;
    int x;

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

public class Main {

    static int l;
    static int[][] map;
    static boolean[][] visit;
    static int[][] dr = { { -2, -1 }, { -2, 1 }, { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 }, { 2, -1 }, { 2, 1 } };
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int k = 0; k < t; k++) {
            l = Integer.parseInt(br.readLine());
            map = new int[l][l];
            visit = new boolean[l][l];

            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int endY = Integer.parseInt(st.nextToken());
            int endX = Integer.parseInt(st.nextToken());

            bfs(y, x, endY, endX);

        }
        System.out.print(sb);
    }

    public static void bfs(int y, int x, int endY, int endX) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(y, x));
        visit[y][x] = true;

        while (!q.isEmpty()) {
            Node node = q.poll();
            // 목표점 도달
            if (node.y == endY && node.x == endX) {
                sb.append(map[node.y][node.x]).append("\n");
                return;
            }

            for (int i = 0; i < dr.length; i++) {
                int ny = node.y + dr[i][0];
                int nx = node.x + dr[i][1];

                // 범위를 벗어나거나 방문했을 때
                if (ny < 0 || ny >= l || nx < 0 || nx >= l || visit[ny][nx]) {
                	continue;
                }
                // 다음 턴 큐에 넣고
                q.add(new Node(ny, nx));
                // 방문처리
                visit[ny][nx] = true;
                // 맵에 이동 숫자 저장
                map[ny][nx] = map[node.y][node.x] + 1;
            }
        }
    }

}