[백준(Baekjoon)][자바(java)] 7562 : 나이트의 이동 / 그래프와 순회

 

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

7562번: 나이트의 이동

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int l, x_start, y_start, x_end, y_end, cell[], x, y, c, nx, ny, nc, i;
		Deque<int[]> queue; // x, y, cnt
		boolean visited[][];
		final int dx[] = {-1, -1, -2, -2, 1, 1, 2, 2}, 
			dy[] = {-2, 2, -1, 1, -2, 2, -1, 1}, s = dx.length;
		StringBuilder sb = new StringBuilder();
		loop : 
		while (t-- > 0) {
			l = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			x_start = Integer.parseInt(st.nextToken());
			y_start = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			x_end = Integer.parseInt(st.nextToken());
			y_end = Integer.parseInt(st.nextToken());
			if (x_start == x_end && y_start == y_end) {
				sb.append(0 + "\n");
				continue loop;
			}
			queue = new ArrayDeque<>();
			visited = new boolean[l][l];
			queue.add(new int[]{x_start, y_start, 0});
			visited[x_start][y_start] = true;
			while (!queue.isEmpty()) {
				cell = queue.remove();
				x = cell[0];
				y = cell[1];
				c = cell[2];
				nc = c + 1;
				for (i = 0; i < s; i++) {
					nx = x + dx[i];
					ny = y + dy[i];
					if (nx < 0 || nx >= l || ny < 0 || ny >= l || visited[nx][ny])
						continue;
					if (nx == x_end && ny == y_end) {
						sb.append(nc + "\n");
						continue loop;
					}
					queue.add(new int[]{nx, ny, nc});
					visited[nx][ny] = true;
				}
			}
		}
		br.close();
	
		System.out.println(sb.toString());
	}
}