[백준] 7562. 나이트의 이동 (Java)

 

🔒 문제

7562번: 나이트의 이동

 

 

🔑 알고리즘

BFS

 

 

💡  풀이

나이트가 8방향으로 이동할 수 있으므로

BFS를 통해 8방향으로 탐색하며 이동횟수를 센다.

 

 

✏️ 코드

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[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
	static int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };

	public static void main(String[] args) throws NumberFormatException, 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 I = Integer.parseInt(br.readLine());
			boolean[][] visited = new boolean[I][I];

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int knightY = Integer.parseInt(st.nextToken());
			int knightX = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine(), " ");
			int targetY = Integer.parseInt(st.nextToken());
			int targetX = Integer.parseInt(st.nextToken());

			Queue<Knight> queue = new LinkedList<>();
			queue.add(new Knight(knightY, knightX, 0));
			visited[knightY][knightX] = true;

			while (!queue.isEmpty()) {

				Knight cur = queue.poll();

				if (cur.y == targetY && cur.x == targetX) {
					sb.append(cur.count).append("\n");
					break;
				}

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

					if (ny < 0 || ny >= I || nx < 0 || nx >= I || visited[ny][nx])
						continue;

					visited[ny][nx] = true;
					queue.add(new Knight(ny, nx, cur.count + 1));
				}
			}
		}

		System.out.println(sb);
	}

	static class Knight {
		int y, x, count;

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