7562_나이트의 이동 (JAVA)

7562번: 나이트의 이동

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static class XY{
		int x; int y;
		public XY(int x, int y){
			this.x = x; this.y = y;
		}
	}
	static int[] dx = {-2, -2, -1, 1, 2, 2, 1, -1};
	static int[] dy = {-1, 1, 2, 2, 1, -1, -2, -2};
	static int n;
	static int[][] chess;
	static boolean[][] visited;
	static XY end; //도착 지점

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testcase = Integer.parseInt(br.readLine());
		for(int i=0; i<testcase; i++){
			n = Integer.parseInt(br.readLine());
			visited = new boolean[n][n];
			chess = new int[n][n];

			StringTokenizer st1 = new StringTokenizer(br.readLine());
			XY start = new XY(Integer.parseInt(st1.nextToken()),Integer.parseInt(st1.nextToken()));

			st1 = new StringTokenizer(br.readLine());
			end = new XY(Integer.parseInt(st1.nextToken()),Integer.parseInt(st1.nextToken()));

			bfs(start.x, start.y);
			System.out.println(chess[end.x][end.y]);
		}
	}

	private static void bfs(int a, int b){
		Queue<XY> q = new LinkedList<>();
		q.offer(new XY(a,b));
		visited[a][b] = true;

		if(a==end.x && b==end.y)
			return;

		while(!q.isEmpty()){
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();

			for(int i=0; i<8; i++) {
				int xx = x + dx[i];
				int yy = y + dy[i];

				if (xx >= 0 && xx < n && yy >= 0 && yy < n) {
					if (!visited[xx][yy]){
						q.offer(new XY(xx,yy));
						visited[xx][yy] = true;
						chess[xx][yy] = chess[x][y]+1;
					}
				}
			}
		}
	}
}

 

 

나이트가 이동할 수 있는 위치는 다음의 8가지 경우이다. 

 

 

시작 위치 에서부터 도착 위치까지 bfs 탐색을 한다.

도착 위치까지만 가면 되므로, chess[][] 배열은 0으로 채워진(초기화된) 상태로 bfs 탐색을 한다.

 

나이트가 이동할 때마다 == 큐에 push할 때마다

chess[xx][yy] = chess[x][y]+1 을 해준다. 즉, 이전 위치에 +1해서 넣어준다.

 

- n=8, start(0,0), end(7,0) 일때, bfs탐색 후의 chess[][] 는 다음과 같이 된다.