Baekjoon 7562 나이트의 이동 JAVA

7562번: 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이

기본적인 사방 혹은 팔방탐색에서 상하좌우 값이 아닌 나이트가 움직일 수 있는 값을 넣어주면 된다.

32번 라인의 도착 if문의 경우, BFS 특성상 적게 움직이는 횟수가 먼저 도착하기에, 따로 검증을 하지 않고 바로 출력하면된다.

코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		int [] dx = {-2,-1,1,2,2,1,-1,-2}, dy= {1,2,2,1,-1,-2,-2,-1};
		
		for (int tc = 0; tc < TC; tc++) {
			int l = Integer.parseInt(br.readLine());
			boolean[][] chk = new boolean[l][l];
			int sx, sy, ex,ey;
			StringTokenizer st = new StringTokenizer(br.readLine());
			sx = Integer.parseInt(st.nextToken());
			sy = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			ex = Integer.parseInt(st.nextToken());
			ey = Integer.parseInt(st.nextToken());
			Queue<Point> q = new LinkedList<Point>();
			Queue<Integer> cnt = new LinkedList<>();
			q.add(new Point(sx,sy));
			cnt.add(0);
			chk[sx][sy]=true;
			while(q.size()>0) {
				Point pos = q.poll();
				int cur=cnt.poll();
				if(pos.x==ex && pos.y==ey)
				{
					System.out.println(cur);
					break;
				}
				for(int i=0;i<8;i++) {
					if(pos.x+dx[i]<0 || pos.x+dx[i]>=l || pos.y+dy[i]<0 || pos.y+dy[i]>=l || chk[pos.x+dx[i]][pos.y+dy[i]])
						continue;
					q.add(new Point(pos.x+dx[i],pos.y+dy[i]));
					cnt.add(cur+1);
					chk[pos.x+dx[i]][pos.y+dy[i]]=true;
				}
			}
		}
	}
}