[알고리즘] 백준 7562번 나이트의 이동 :: 우유

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

7562번: 나이트의 이동

---

동서남북으로 방향이 정해져있던 기존 BFS 와 다르게 나이트의 이동경로 8방향으로 dx,dy 배열을 초기화해주면 되는 간단한 문제이다

---

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

	static int N, l;
	static int map[][];
	static boolean visited[][];
	static int startX, startY, endX, endY;
	static int dy[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
	static int dx[] = { -1, 1, -2, 2, -2, 2, -1, 1 };

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		while (N-- != 0) {
			l = Integer.parseInt(br.readLine());

			map = new int[l][l];
			visited = new boolean[l][l];

			st = new StringTokenizer(br.readLine());

			startY = Integer.parseInt(st.nextToken());
			startX = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine());

			endY = Integer.parseInt(st.nextToken());
			endX = Integer.parseInt(st.nextToken());

			System.out.println(BFS(startY, startX));
		}
	}

	static int BFS(int y, int x) {
		
		if (y == endY && x == endX)
			return 0;
		
		Queue<int[]> qu = new LinkedList<int[]>();
		visited[y][x] = true;

		map[y][x] = 0;
		qu.add(new int[] { y, x });

		while (!qu.isEmpty()) {
			int[] temp = qu.poll();

			int curY = temp[0];
			int curX = temp[1];

			if (curY == endY && curX == endX)
				return map[endY][endX];

			for (int k = 0; k < 8; k++) {
				int ny = curY + dy[k];
				int nx = curX + dx[k];

				if (ny < 0 || nx < 0 || l-1 < ny || l-1 < nx)
					continue;

				if (visited[ny][nx])
					continue;

				qu.add(new int[] { ny, nx });
				map[ny][nx] = map[curY][curX] + 1;
				visited[ny][nx] = true;

			}
		}
		return -1;
	}
}