[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을 출력한다.

Code

package day0128;

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 BOJ_16948 {
	
    static int N; // 체스판 크기
    static int dx [] = {-2,-2,0,0,2,2}; // 이동
    static int dy [] = {-1,1,-2,2,-1,1}; 
    static boolean visited[][]; // 방문 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 체스판 크기 입력
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] position = new int[4]; // r1, c1, r2, c2 저장할 배열
        for (int i = 0; i < 4; i++) {
        	position[i] = Integer.parseInt(st.nextToken());
        }
        
        bfs(position[0],position[1],position[2],position[3]);
        
    }
    public static void bfs(int r1, int c1, int r2, int c2) {
        visited = new boolean[N+1][N+1]; // 초기화
        Queue<Node>queue = new LinkedList<>();
        queue.add(new Node(r1,c1,0));
        
        while(!queue.isEmpty()) {
            Node now = queue.poll();
            if(now.x ==r2 && now.y==c2) {
                System.out.println(now.count);
                return ;
            }
            for(int i=0; i<6; i++) {
                int nx = now.x+dx[i];
                int ny = now.y+dy[i];
                
                if(nx<0 || ny<0 || nx>N || ny>N) continue;
                if(!visited[nx][ny]) {
                	queue.add(new Node(nx,ny,now.count+1));
                    visited[nx][ny] = true;
                }
            }
        }
        System.out.println(-1);
    }
}

class Node{
    int x, y, count;
    Node(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}

Today I Learned

BFS를 복습할 수 있는 좋은 문제였다