문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

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

풀이

bfs를 사용하여 이전 값의 +1 해주는 형태로 최단 경로를 구하면 되는 문제이다. 이동할 수 있는 경우가 총 8가지이기 때문에 8가지 방향에 대해서 bfs를 해주면 되는 것이다.

2차원 int형 배열을 만들어 -1로 초기화 해준 뒤 시작 좌표를 0으로 두고 bfs를 수행 할 때마다 이전 값의 + 1를 해주면서 진행하면 된다.

최종적으로 도착 좌표의 값을 출력하면 문제를 해결할 수 있다.

소스

import java.util.*;

class Node {
	private int x;
	private int y;

	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}
}

public class Main {
	public static int t, l;

	public static int[][] map;

	// 그림의 왼쪽 위부터 시계방향으로
	public static int[] dx = { -1, -2, -2, -1, 1, 2, 2, 1 };
	public static int[] dy = { -2, -1, 1, 2, 2, 1, -1, -2 };

	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(x, y));
		map[x][y] = 0;

		while (!q.isEmpty()) {
			Node node = q.poll();
			x = node.getX();
			y = node.getY();

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

				// 범위 내에서
				if (nx >= 0 && nx < l && ny >= 0 && ny < l) {
					if (map[nx][ny] == -1) {
						map[nx][ny] = map[x][y] + 1;
						q.offer(new Node(nx, ny));
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		t = sc.nextInt();

		while (t-- > 0) {
			l = sc.nextInt();
			map = new int[l][l];

			// 시작 좌표
			int sx = sc.nextInt();
			int sy = sc.nextInt();
			// 도착 좌표
			int ex = sc.nextInt();
			int ey = sc.nextInt();

			for (int i = 0; i < l; i++) {
				Arrays.fill(map[i], -1);
			}

			bfs(sx, sy);
			System.out.println(map[ex][ey]);

		}

	}

}