문제

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

---

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다.
첫째 줄에는 체스판의 한 변의 길이 l이 주어진다.
체스판의 크기는 l × l이다.
둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

---

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

---

풀이

제한조건

• l(4 ≤ l ≤ 300)

접근방법

탐색

최소 이동횟수를 찾는 문제이므로 BFS로 탐색하면 된다.

12시 방향을 기준으로 우측으로 돌며 8가지 방향을 정의해주고 탐색해주자.

int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

이제 BFS를 수행하며, 도착지에 도달하였는지 체크해주면 된다.

---

코드

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

public class Main {
	static int I;
	static int[][] map, visit;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		// input
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = stoi(in.readLine());

		for (int tc = 0; tc < T; ++tc) {
			I = stoi(in.readLine());
			String[] inputs = in.readLine().split(" ");
			int sx = stoi(inputs[0]);
			int sy = stoi(inputs[1]);
			inputs = in.readLine().split(" ");
			int ex = stoi(inputs[0]);
			int ey = stoi(inputs[1]);
			int count = getMoveCount(sx, sy, ex, ey);
			sb.append(count).append("\n");
		}
		System.out.println(sb);
	}

	static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
	static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

	private static int getMoveCount(int sx, int sy, int ex, int ey) {
		map = new int[I][I];
		visit = new int[I][I];

		Queue<int[]> q = new ArrayDeque<>();
		visit[sx][sy] = 1;
		q.add(new int[] {sx, sy});
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cx = cur[0];
			int cy = cur[1];
			if (cx == ex && cy == ey)
				break;
			for (int d = 0; d < 8; ++d) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (!isInRange(nx, ny))
					continue;
				if (visit[nx][ny] > 0)
					continue;
				visit[nx][ny] = visit[cx][cy] + 1;
				q.add(new int[] {nx, ny});
			}
		}

		return visit[ex][ey] - 1;
	}

	public static boolean isInRange(int x, int y) {
		if (0 <= x && x < I && 0 <= y && y < I)
			return true;
		return false;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}