백준 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번부터 시작한다.

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

접근 방법

(r1, c1)에서 (r2, c2)로 이동하는 최단거리를 구하는 문제이다.
BFS는 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 시작 점에서 각 점에 처음 도착할 때 까지 걸리는 이동 횟수가 최단 거리가 된다.
따라서, NxN 크기의 방문 여부 2차원 배열을 통하여, 목표하는 점에 처음 도착했을 때의 이동 횟수를 구하면, 최소 이동 횟수를 구하게 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int sy, sx, ty, tx;
	static boolean[][] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	stk = new StringTokenizer(br.readLine());
    	
    	sy = stoi(stk.nextToken());
    	sx = stoi(stk.nextToken());
    	ty = stoi(stk.nextToken());
    	tx = stoi(stk.nextToken());
    	
    	vis = new boolean[n][n];
    	
    	result = BFS(sy,sx);
    	
    	System.out.println(result);
    	br.close();
	}
	// 데스나이트의 이동 방향
	static int[] dy = {-2,-2,0,0,2,2};
	static int[] dx = {-1,1,-2,2,-1,1};	
	
	public static int BFS(int y, int x) {
		vis[y][x] = true;
		
		Queue<int[]> queue = new LinkedList<int[]>();
		// 각 점의 위치, 그 점까지 이동하기 까지의 최소 횟수
		queue.add(new int[] {y,x,0});
		
		int[] q;
		int ny,nx, cnt;
		while(!queue.isEmpty()) {
			q = queue.poll();
			y = q[0];
			x = q[1];
			cnt = q[2] + 1;		// 이동 횟수를 늘린다.
			
			for(int i = 0; i < 6; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				
				if(isIn(ny,nx) && !vis[ny][nx]) {
					// 목표 지점에 도착하면, 그 횟수를 출력
					if(ny == ty && nx == tx) {
						return cnt;
					}
					vis[ny][nx] = true;
					queue.add(new int[] {ny, nx, cnt});
				}
			}
		}
		return -1;
	}
	
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

이전에 비슷한 문제를 풀어보아, 쉽게 해결하였다.

개선할 점

없습니다.