[백준] 16948 데스 나이트

문제 출처: www.acmicpc.net/problem/16948

16948번: 데스 나이트

: 크기가 NxN인 체스판에서 r1, c1, r2, c2가 주어질 때 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해야 한다.

: 최소 이동 횟수이기 때문에 bfs 방식을 생각할 수 있다. 

: 데스 나이트가 이동하는 규칙은 델타배열로 만들어 사용할 수 있도록 한다.

: 도착점이 주어져 있기 때문에 체스판의 지점들을 방문하던 중 도착점에 도달하면 그 때까지 걸린 횟수를 반환한다.

: 도착 지점에 도달하지 못한다면 중간에 return 되지 않으므로 도착점까지 해당 규칙으로 갈 수 없다는 뜻이 된다. 따라서 -1을 반환한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 데스나이트 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[][] map;
	static int startR, startC, endR, endC;
	static class Point{
		int r, c, cnt;

		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		st = new StringTokenizer(br.readLine());
		startR = Integer.parseInt(st.nextToken());
		startC = Integer.parseInt(st.nextToken());
		endR = Integer.parseInt(st.nextToken());
		endC = Integer.parseInt(st.nextToken());
		int res = bfs(startR, startC);
		System.out.println(res);
	}
	static int[] dr = {-2, -2, 0, 0, 2, 2};
	static int[] dc = {-1, 1, -2, 2, -1, 1};
	private static int bfs(int r, int c) {
		boolean[][] v = new boolean[N][N];
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(r, c, 0));
		v[r][c] = true;
		
		while(!q.isEmpty()) {
			Point cur = q.poll();
			if(cur.r == endR && cur.c == endC) {
				return cur.cnt;
			}
			for(int i = 0 ; i < 6; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= N || v[nr][nc]) continue;
				q.offer(new Point(nr, nc, cur.cnt+1));
				v[nr][nc] = true;
			}
		}
		return -1;
	}
}