백준 7562 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //방향 정보
        int[][] directions = new int[][]{{1, 2}, {2, 1}, {1, -2}, {2, -1}, {-1, 2}, {-2, 1}, {-1, -2}, {-2, -1}};

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            
            //L, 시작점, 도착점 입력 받기
            int l = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] start = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            st = new StringTokenizer(br.readLine());
            int[] end = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            //BFS 탐색
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{start[0], start[1], 0});

            boolean[][] visited = new boolean[l][l];
            int answer = 0;
            while (!q.isEmpty()) {
                int[] ptr = q.poll();

                if (ptr[0] == end[0] && ptr[1] == end[1]) {
                    answer = ptr[2];
                    break;
                }

                if(visited[ptr[0]][ptr[1]])
                    continue;
                visited[ptr[0]][ptr[1]]=true;

                for(int[] d:directions){
                    int dx = ptr[0] + d[0];
                    int dy = ptr[1] + d[1];

                    if(dx<0 || dy<0 || dx>=l || dy>=l || visited[dx][dy])
                        continue;

                    q.add(new int[]{dx, dy, ptr[2]+1});
                }
            }

            bw.write(answer+"\n");
        }

        bw.flush();
    }
}

---

해결 과정

1. 시작점에서 BFS 탐색으로 도착점까지 탐색한다.

2. 😁