[Java] 백준 7526 : 나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

 

---

 

 

import java.util.*;

public class Main {
	
	static class Point{
		int x,y;
		Point(int x,int y){
			this.x=x;
			this.y=y;
		}
	}//class Point
	
	static int[][] arr;
	static boolean[][] visit;
	static int T,N;
	//나이트가 움직일 수 있는 방향 
	static int[] dx = {-2,-1,2,1,2,1,-2,-1};
	static int[] dy = {1,2,1,2,-1,-2,-1,-2};
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		T=Integer.parseInt(sc.next());	//테스트 케이스
		
		for(int i=0;i<T;i++) {			
			N = sc.nextInt();	//체스판 한 변의 길이		
			arr= new int[N][N];		//체스판
			visit= new boolean[N][N];
			Point tmp=new Point(sc.nextInt(),sc.nextInt());
			Point arrive=new Point( sc.nextInt(),sc.nextInt());
			bfs(tmp,arrive);
			System.out.println(arr[arrive.x][arrive.y]);
		}
		
	}// main()
	
	static void bfs(Point tmp,Point end) {
		Queue<Point> qu = new LinkedList<>();
		
		qu.add(tmp);
		visit[tmp.x][tmp.y]=true;
		
		while(!qu.isEmpty()) {
						
			Point p = qu.poll();
			int x1= p.x;
			int y1= p.y;
			
			if(x1==end.x&&y1==end.y) {
				return;
			}
			
			for(int i=0;i<8;i++) {
				int nX=x1+dx[i];
				int nY=y1+dy[i];
				
				if(nX>=0&&nX<N&&nY>=0&&nY<N&&!visit[nX][nY]) {
					qu.add(new Point(nX,nY));
					visit[nX][nY]=true;
					arr[nX][nY]=arr[x1][y1]+1;
				}
			}
		}
	}//bfs()
	
}// class Main