<백준> 7562번 자바 알고리즘[BFS]

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



public class Main
{
    
    static class Loc {
    int x;
    int y;
    
    public Loc(int x, int y){
        this.x = x;
        this.y = y;
    }
}
    static int start_x, start_y, end_x, end_y;
    static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1}; 
    static Queue<Loc> q = new LinkedList<>();
    static boolean[][] visited;
    static int[][] arr;
    static int i;
    
     
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		// 반복 횟수 
		for(int a = 0; a < t; a++){
		   
		    i = Integer.parseInt(br.readLine());
		    // 체스판 만들기 
		    arr = new int[i][i];
		    // 방문기록 만들기 
		    visited = new boolean[i][i];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
		   
		    start_x = Integer.parseInt(st.nextToken());
		    start_y = Integer.parseInt(st.nextToken());
		    
		    st = new StringTokenizer(br.readLine());
		      
		    end_x = Integer.parseInt(st.nextToken());
		    end_y = Integer.parseInt(st.nextToken());
		    //총 8가지 경우 

		    
		    
		    bfs(new Loc(start_x, start_y));
		    
		}
		

		   
	}
	
	static void bfs(Loc loc) {
	    
	     q.clear();
	     visited[loc.x][loc.y] = true;
	     q.add(loc);
	    
	     while(!q.isEmpty()){
		        
		        // q에서 하나 꺼내기 
		        Loc now = q.poll();
		        
		        
		        // 도달 했을 때 
		        if(now.x == end_x && now.y == end_y){
		            System.out.println(arr[now.x][now.y]);
		            break;
		    }
		        
		        // 여덟가지 경우 
		        for(int k = 0; k < 8; k++){
		            int nx = now.x + dx[k];
		            int ny = now.y + dy[k];
		            
		            // 범위 벗어 났을 때 
		            if(nx < 0 || nx >= i || ny < 0 || ny >= i) continue;
		            
		            // 만약 방문 안했을 때 
		            if(!visited[nx][ny]){
		                visited[nx][ny] = true;
		                arr[nx][ny] = arr[now.x][now.y] + 1;
		                q.add(new Loc(nx, ny));
		            }
		        }
		        
		        
		    }
	}
	

}

입력 케이스 T 
첫째 줄 : 체스판 길이 I (I x I)
둘째 줄 : 나이트가 현재 있는 칸 
셋째 줄 : 이동하려는 칸 

구하는 것 : (최소) 몇번 움직여야 도착 하는지 
=> bfs 구현 

현재 x, y 가 도착점 end_x, end_y에 도달하면 출력

다음 점으로 이동할때 마다 arr값에 이전값 + 1 하기로 구현하면 될듯

주의 : 평소처럼 상하좌우 +1이 아니라 나이트 특성처럼 이동 해야 됨 

dx: {1, 2, 2, 1, -1, -2, -2, -1}
dy: {-2, -1, 1, 2, 2, 1, -1, -2}