Baekjoon7562: 나이트의 이동

나이트의 이동

1 초

256 MB

32085

15702

11759

48.059%

문제

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

입력

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

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

출력

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

풀이

DFS(재귀호출)로 생각하는 순간 아찔해지는 문제이다.

BFS(큐)를 이용한 최소경로 구하기

BFS(큐)로 나이트가 움직일 수 있는 8 방향을 모두 스택에 넣어주는 것을 반복해 해당 경로에 도착하자마자 출력하는 방식으로 구성하면 될 것이다.

각 테스트 케이스

첫째줄: 크기(I x I)

둘째줄: 현재 위치

셋째줄: 도착하고 싶은 위치

참고사항

값을 찾는 순간 while 반복문은 종료되도록하며 방문기록배열(check[][])를 따로 사용하지 않는다.

import java.util.*;
public class Main {
	static int[][] arr; //check[][] 배열을 사용x
	static int T,I,X,Y; //I: 체스판 크기, X,Y: 도착지점
	static int[] dx = {1,-1,2,-2,1,-1,2,-2}; //8방향
	static int[] dy = {2,2,1,1,-2,-2,-1,-1};
	static Queue<int[]> queue = new LinkedList<int[]>();
	public static void bfs() {
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			int nowX = now[0]; 
			int nowY = now[1];
			if(nowX ==X && nowY==Y) { //도착지점 X, Y에 도달하면 반복문 break
				break;
			}
			for(int i=0;i<8;i++) {
				int nextX = nowX + dx[i];
				int nextY = nowY + dy[i];
				
				if(nextY<0 || nextX<0 || nextX>=I || nextY>=I
					|| arr[nextX][nextY]!=0) {
					continue;
				}
				queue.add(new int[] {nextX,nextY});
				arr[nextX][nextY]=arr[nowX][nowY]+1;
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T=sc.nextInt();
		while(T-->0) {
			I=sc.nextInt();
			arr = new int[I][I];
			int startX = sc.nextInt();
			int startY = sc.nextInt();
			arr[startX][startY]=1;
			queue.add(new int[] {startX,startY});
			X=sc.nextInt();
			Y=sc.nextInt();
			bfs();
			System.out.println(arr[X][Y]-1);
			queue.clear();
		}
}}