[백준] 7562번 : 나이트의 이동

문제

 

 

접근 방식

기존 BFS를 이용한 문제들과 똑같은 방법으로 풀면 되는 문제지만

이동 방향이 앞뒤양옆이 아닌 나이트가 이동할 수 있는

8가지의 방향을 탐색해주면 된다.

 

int[] knightX = {2, 2, 1, 1, -1, -1, -2, -2};
int[] knightY = {1, -1, 2, -2, 2, -2, 1, -1};

 

위와 같이 나이트의 이동 방법을 배열에 기록해두면 편하다.

 

이제 저 배열을 순회하면서 현재 위치부터 BFS를 이용해 탐색을 하면 되고

이동한 위치가 목표 지점과 같은 경우에는 이동 횟수를 기록하고

탐색을 종료해주면 된다.

풀이

public class Main {

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

		int[] knightX = {2, 2, 1, 1, -1, -1, -2, -2};
		int[] knightY = {1, -1, 2, -2, 2, -2, 1, -1};

		int n = Integer.parseInt(br.readLine());

		while (n-- > 0) {
			int l = Integer.parseInt(br.readLine());
			boolean[][] isVisited = new boolean[l][l];

			st = new StringTokenizer(br.readLine(), " ");
			Knight now = new Knight(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

			st = new StringTokenizer(br.readLine(), " ");
			Knight target = new Knight(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

			Queue<Knight> knights = new LinkedList<>();
			knights.offer(now);
			isVisited[now.x][now.y] = true;

			if (now.x == target.x && now.y == target.y) {
				sb.append(0).append("\n");
				continue;
			}

			out:
			while (!knights.isEmpty()) {
				Knight cur = knights.poll();

				for (int i = 0; i < 8; i++) {
					int x = cur.x + knightX[i];
					int y = cur.y + knightY[i];

					if (x < 0 || x >= l || y < 0 || y >= l) continue;
					if (isVisited[x][y]) continue;

					isVisited[x][y] = true;

					if (x == target.x && y == target.y) {
						sb.append(cur.moves + 1).append("\n");
						break out;
					}

					knights.offer(new Knight(x, y, cur.moves + 1));
				}
			}
		}

		System.out.println(sb);
	}

	private static class Knight {
		int x;
		int y;
		int moves;

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