문제

이해

그래프 상에서 나이트가 이동한다. 나이트는 위의 문제와 같이 이동할 수 있다.

IxI의 그래프에서 나이트가 시작점에서 도착점까지 이동할 수 있는 최소 이동횟수를 출력해야 한다.

접근

최소 이동 횟수와 같은 최단거리는 BFS로 해결할 수 있다.

BFS의 depth를 이동횟수라고 하고 depth를 키우면서 이동하는 과정을 지켜본다.

이 때, 나이트가 도착점에 도착하면 BFS를 종료하고 이 때의 depth를 출력하면 된다.

주의할 점은 나이트가 이동하는 방식인데 이전에 풀었던 최단거리 BFS 문제는 상하좌우, 혹은 대각선으로 움직였지만 나이트는 그림처럼 이동한다는 것을 코드에 포함해야 한다.

코드

package java_baekjoon;

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

public class prob7562 {
    static int T;
    static int I;
    static boolean[][] visited;
    static int[] d_row = { -2, -1, 1, 2, 2, 1, -1, -2 };
    static int[] d_col = { 1, 2, 2, 1, -1, -2, -2, -1 };

    static class coordinate {
        int row;
        int col;
        int depth;

        public coordinate(int row, int col, int depth) {
            this.row = row;
            this.col = col;
            this.depth = depth;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        

        T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            I = Integer.parseInt(br.readLine());
            visited = new boolean[I][I];

            st = new StringTokenizer(br.readLine());
            coordinate start_cdnt = new coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
            st = new StringTokenizer(br.readLine());
            coordinate arrival_cdnt = new coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

            Queue<coordinate> q = new LinkedList<>();
            q.add(start_cdnt);
            visited[start_cdnt.row][start_cdnt.col] = true;

            while(!q.isEmpty()){
                coordinate now = q.poll();

                if(now.row == arrival_cdnt.row && now.col == arrival_cdnt.col){
                    System.out.println(now.depth);
                    break;
                }

                for(int i=0;i<8;i++){
                    int next_row = now.row + d_row[i];
                    int next_col = now.col + d_col[i];

                    if(next_row >= 0 && next_row < I && next_col >= 0 && next_col < I && !visited[next_row][next_col]){
                        q.add(new coordinate(next_row, next_col, now.depth + 1));
                        visited[next_row][next_col] = true;
                    }
                }
            }
        }
    }
}

coordinate 클래스에 depth 멤버 변수를 포함시켰다. 이를 통해 큐에 들어가는 이동가능한 좌표에 나이트의 이동횟수를 저장하였다.

결과