백준 7562 나이트의 이동 (Java)

1. 문제 링크

7562번: 나이트의 이동

 

2. 문제 및 입출력예제

 

3. 문제 풀이

나이트가 움직이는 8방향으로 bfs 탐색을 진행한다.

최소 횟수로 움직여야 하기 때문에 방문했는지 확인하기 위해 visit 배열을 이용했다.

 

사실 1331번 나이트 투어를 풀려고 하는데 나이트가 어떻게 움직이는지 몰라서 이 문제를 먼저 찾아왔다...ㅎ

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2}, dy = {1, 2, 2, 1, -1, -2, -2, -1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			int result = 0;
			int N = Integer.parseInt(br.readLine());
			Queue<Point> queue = new ArrayDeque<>();
			String[] split = br.readLine().split(" ");
			int sx = Integer.parseInt(split[0]);
			int sy = Integer.parseInt(split[1]);
			split = br.readLine().split(" ");
			int ex = Integer.parseInt(split[0]);
			int ey = Integer.parseInt(split[1]);
			boolean[][] visit = new boolean[N][N];
			
			queue.offer(new Point(sx, sy));
			visit[sx][sy] = true;
			
			out:
			while(!queue.isEmpty()) {
				int size = queue.size();
				for(int i=0;i<size;i++) {
					Point now = queue.poll();
					if(now.x == ex && now.y == ey) {
						break out;
					}
					for(int d=0;d<8;d++) {
						int X = now.x+dx[d];
						int Y = now.y+dy[d];
						if(X<0 || X>=N || Y<0 || Y>=N || visit[X][Y]) {
							continue;
						}
						queue.offer(new Point(X, Y));
						visit[X][Y] = true;
					}
				}
				result++;
			}
			
			sb.append(result).append("\n");
		}
		System.out.println(sb);
	}
}