[7562] 나이트의 이동

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

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

// 7562 나이트의 이동
public class Main {
	static int [][] map;
	static Queue<Pair> queue;
	static boolean [][] visited;
	static int I, X, Y, cnt;
	static int[][] temp = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int i=0; i<T; i++) {
			I = sc.nextInt();
			map = new int [I][I];
			visited = new boolean [I][I];
			int x = sc.nextInt();
			int y = sc.nextInt();
			map[x][y] = 1;
			X = sc.nextInt();
			Y = sc.nextInt();
			
			BFS(x, y);
			
//			for(int j=0; j<I; j++) {
//				for(int k=0; k<I; k++) {
//					System.out.print(map[j][k] + " ");
//				}
//				System.out.println();
//			}
			System.out.println(map[X][Y]-1);
			
		}
	}
	public static void BFS(int x, int y) {
		queue = new LinkedList<Pair>();
		queue.offer(new Pair(x, y));
		visited[x][y] = true;
		
		
		while(!queue.isEmpty()) {
			Pair current = queue.poll();
			
			for(int i=0; i<8; i++) {
				int nextX = current.x + temp[i][0];
				int nextY = current.y + temp[i][1];
				if(isInside(nextX, nextY)&&visited[nextX][nextY] == false) {
					map[nextX][nextY] = map[current.x][current.y]+1; 
					if(nextX == X && nextY == Y) return;
					queue.offer(new Pair(nextX, nextY));
					visited[nextX][nextY] = true;
				}
			}
		}
	}
	
	public static boolean isInside(int x, int y) {
		if(x>=0&&x<I&&y>=0&&y<I) return true;
		else return false;
	}
}

class Pair {
	int x;
	int y;
	Pair(int x, int y){
		this.x=x;
		this.y=y;
	}
}

---

문제를 읽어보면 나이트가 목적지까지 몇번 만에 도달할 수 있는지 묻는 것이기 때문에, 최단거리를 구하는 문제와 같은 문제이다. 그래서 BFS로 해결할 수 있다. 나이트가 이동할 수 있는 범위를 보면 (1, 2) (-1, 2) (1, -2) (-1, -2) (2, 1) (-2, 1) (2, -1) (-2, -1) 이렇게 8가지가 나온다. 처음에 고민했던 부분은 하나씩 탐색하면서 목적지에 도착하면 return 하여 멈추는것까지 계산을 하였는데 나이트가 몇번만에 목적지까지 도착하느냐를 생각해내기 어려웠다. 최단거리 문제를 풀었을 때를 생각해봤는데, 나이트가 움직이는 좌표에 전좌표의 값을 계속 더해가주면 쉽게 해결 되는 문제였다. 처음에는 1시간 넘게 고민해도 안풀렸는데, 잠깐 멈추고 다음날 다시 생각해보니까 금방 풀 수 있었다.

< 문제 풀이 >

1. 시작점 x, y와 목적점 X, Y를 입력받고 시작점 x, y에서 BFS를 시작한다.

2. BFS를 하면서 나이트가 이동할 수 있는 8개의 좌표를 모두 확인하는데, 전 좌표에 1을 더해서 나이트가 이동하는 거리를 모두 표시하고, 목적지 X와 Y를 만나면 BFS를 멈춘다.

3. 그리고 map[X][Y]를 출력하면 되는데, 처음 시작에서 카운트를 안해줬기 때문에 -1을 해서 출력한다.