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

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

7562번: 나이트의 이동

 

 

bfs로 풀었다.

 

이동가능한 8가지의 방향으로 다음 위치를 계산하고

다음 위치가 체스판을 넘어가지 않고, 방문한 적 없다면

큐에 넣는다.

 

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 P7562 {

	static int l;
	static int[][] visited;
	static int[] dx= {1,-1,2,-2,-2,2,-1,1};
	static int[] dy= {2,2,1,1,-1,-1,-2,-2};
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T= Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int testCase=0;testCase<T;testCase++) {
			l=Integer.parseInt(br.readLine());
			st= new StringTokenizer(br.readLine());
			int start_x = Integer.parseInt(st.nextToken());
			int start_y = Integer.parseInt(st.nextToken());
			st= new StringTokenizer(br.readLine());
			
			int goal_x = Integer.parseInt(st.nextToken());
			int goal_y = Integer.parseInt(st.nextToken());
			
			visited=new int[l][l];
			bfs(start_x,start_y,goal_x,goal_y);
			System.out.println(visited[goal_x][goal_y]-1);
		}
	}
	private static void bfs(int start_x, int start_y, int goal_x, int goal_y) {

		visited[start_x][start_y]=1;
		Queue<Integer> q_x = new LinkedList<>();
		Queue<Integer> q_y = new LinkedList<>();
		
		q_x.add(start_x);
		q_y.add(start_y);
		
		while(!q_x.isEmpty()) {
			int now_x=q_x.poll();
			int now_y=q_y.poll();
			
			for(int i=0;i<8;i++) {
				int next_x=now_x+dx[i];
				int next_y=now_y+dy[i];
				
				if(next_x<0||next_x>l-1||next_y<0||next_y>l-1)
					continue;
				
				if(visited[next_x][next_y]==0) {
					visited[next_x][next_y]=visited[now_x][now_y]+1;
					if(next_x==goal_x&&next_y==goal_y) {
						return;
					}
					q_x.add(next_x);
					q_y.add(next_y);
					
				}
			}
		}
		
	}
	

}