백준 7562: 나이트의 이동

풀이

• 나이트는 8방향으로 움직일 수 있다.
• visited배열의 초기값은 MAX_VALUE, 나이트가 이동한 뒤의 값은 해당 칸까지의 가장 짧은 거리이다.
• 이동하고자 하는 칸이 이미 방문한 적이 있는 경우, 해당 칸으로 이동한 거리가 visited배열의 값보다 크거나 같은 경우 이동하지 않는다.

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 Problem7562 {
    static int caseNum, size;
    static int[] dirX = new int[]{-2,-1,1,2,1,2,-1,-2};
    static int[] dirY = new int[]{1,2,2,1,-2,-1,-2,-1};
    static int[] startNode = new int[2];
    static int[] endNode = new int[2];
    static int[][] visited;
    static int[] answers;


    public static int bfs(){
        int answer = Integer.MAX_VALUE;

        //시작점과 목적지가 같은 경우
        if(startNode[0] == endNode[0] && startNode[1] == endNode[1]) return 0;

        Queue<int[]> queue = new LinkedList<>();
        visited[startNode[1]][startNode[0]] = 0;
        queue.add(startNode);

        while(!queue.isEmpty()){
            int[] currNode = queue.poll();
            for (int d = 0; d < 8; d++) {
                int newX = currNode[0] + dirX[d];
                int newY = currNode[1] + dirY[d];

                if (newX < 0 || newX >= size || newY < 0 || newY >= size) continue;
                //방문한 곳을 재 방문할 경우 이전보다 방문 횟수가 적은 경우만 방문한다
                if(visited[newY][newX] <= visited[currNode[1]][currNode[0]] + 1) continue;

                //목적지 도착
                if(newY == endNode[1] && newX == endNode[0]){
                    if(answer > visited[currNode[1]][currNode[0]] + 1) answer = visited[currNode[1]][currNode[0]] + 1;
                } else {
                    visited[newY][newX] = visited[currNode[1]][currNode[0]] + 1;
                    queue.add(new int[]{newX, newY});
                }
            }
        }

        return  answer;
    }




    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        caseNum = Integer.parseInt(br.readLine());
        answers = new int[caseNum];
        for(int i = 0; i < caseNum; i++){
            size = Integer.parseInt(br.readLine());

            StringTokenizer startSt = new StringTokenizer(br.readLine(), " ");
            startNode[0] = Integer.parseInt(startSt.nextToken());
            startNode[1] = Integer.parseInt(startSt.nextToken());


            StringTokenizer endSt = new StringTokenizer(br.readLine(), " ");
            endNode[0] = Integer.parseInt(endSt.nextToken());
            endNode[1] = Integer.parseInt(endSt.nextToken());

            visited = new int[size][size];

            for(int[] a : visited){
                Arrays.fill(a, Integer.MAX_VALUE);
            }

            answers[i] = bfs();

        }

        for(int i : answers){
            System.out.println(i);
        }

    }
}