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

🎈문제

문제링크

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

🎈입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

🎈출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

🎈접근방법

1. 나이트가 이동할 수 있는 좌표를 미리 만들어 놓는다.
2. bfs 방법을 통해서 나이트가 이동할 수 있을 좌표들을 queue에 넣고 queue가 빌 때까지 반복을 한다.
3. 원하는 좌표에 도착했을 때 그 좌표에 해당하는 나이트가 가지고 있는 count를 반납한다.

🎈코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int T;
    // mx,my : 나이트가 움직일 수 있는 좌표
    static int[] mx = {-1,-2,-2,-1, 1, 2, 2, 1}; 
    static int[] my = {-2,-1, 1, 2, 2, 1,-1,-2};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int t=0; t<T; t++){
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            int endX = Integer.parseInt(st.nextToken());
            int endY = Integer.parseInt(st.nextToken());
            
            int[][] map = new int[N][N];
            boolean[][] visited = new boolean[N][N];
            
            int c = bfs(N,startX, startY, endX, endY, map, visited);
            sb.append(c).append('\n');
        }
        System.out.println(sb.toString());
    }
    static int bfs(int size,int startX, int startY, int endX, int endY, int[][] map, boolean[][] visited){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(startX,startY,0));
        visited[startX][startY] = true;

        while(!queue.isEmpty()){
            Node now = queue.poll();
            if(now.x==endX && now.y==endY){
                return now.count;
            }
            for(int i=0; i<8; i++){
                int px = now.x+mx[i];
                int py = now.y+my[i];
                if(px>=0 && py>=0 && px<size && py<size){
                    if(!visited[px][py]){
                        queue.add(new Node(px,py,now.count+1));
                        visited[px][py] = true;
                    }
                }
            }
        }
        return -1;
    }
    static class Node{
        int x,y;
        int count;
        public Node(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}