Baekjoon 16948 데스 나이트 JAVA

16948번: 데스 나이트

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

풀이

2022.04.13 - [Algorithm/Baekjoon] - Baekjoon 7562 나이트의 이동 JAVA

BFS에서 탐색 방법을 주어진 형태대로 넣고 탐색을 한다.

코드

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 n=Integer.parseInt(br.readLine());
		StringTokenizer st= new StringTokenizer(br.readLine());
		int r1=Integer.parseInt(st.nextToken()), c1=Integer.parseInt(st.nextToken());
		int r2=Integer.parseInt(st.nextToken()), c2=Integer.parseInt(st.nextToken());
		int [] dx= {-2,-2,0,0,2,2}, dy= {-1,1,-2,2,-1,1};
		int [][] map = new int[n][n];
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=-1;
		Queue<int []>q = new LinkedList<int[]>();
		q.add(new int [] {r1,c1,0});
		map[r1][c1]=0;
		while(q.size()>0) {
			int [] temp = q.poll();
			int x = temp[0],y = temp[1], cnt=temp[2];
			if(x==r2 && y==c2)
				break;
			for(int i=0;i<6;i++) {
				if(x+dx[i]<0 || x+dx[i]>=n || y+dy[i]<0 ||y+dy[i]>=n)
					continue;
				if(map[x+dx[i]][y+dy[i]]>0)
					continue;
				q.add(new int[] {x+dx[i], y+dy[i], cnt+1});
				map[x+dx[i]][y+dy[i]]=cnt+1;
			}
		}
		System.out.println(map[r2][c2]);
	}
}