[백준 16948] 데스 나이트 - JAVA // le_effort

데스 나이트

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	1881	1296	1089	69.407%

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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을 출력한다.

예제 입력 1 복사

xxxxxxxxxx
7
6 6 0 1

예제 출력 1 복사

xxxxxxxxxx
4

예제 입력 2 복사

xxxxxxxxxx
6
5 1 0 5

예제 출력 2 복사

xxxxxxxxxx
-1

예제 입력 3 복사

xxxxxxxxxx
7
0 3 4 3

예제 출력 3 복사

2

 

 

풀이

기본 bfs 문제였습니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class Main {
    static int n,cnt;
    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());
        
        
        String [] t = br.readLine().split(" ");
        int r1 = Integer.parseInt(t[0]);
        int c1 = Integer.parseInt(t[1]);
        int r2 = Integer.parseInt(t[2]);
        int c2 = Integer.parseInt(t[3]);
        
        bfs(r1,c1,r2,c2);
        
    }
    public static void bfs(int r1, int c1, int r2, int c2) {
        visited = new boolean[n+1][n+1];
        Queue<Node>q = new LinkedList<>();
        q.add(new Node(r1,c1,0));
        
        while(!q.isEmpty()) {
            Node a = q.poll();
            if(a.x ==r2 && a.y==c2) {
                System.out.println(a.cnt);
                return ;
            }
            for(int i=0; i<6; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                
                if(isRange(nx,ny) && !visited[nx][ny]) {
                    q.add(new Node(nx,ny,a.cnt+1));
                    visited[nx][ny] = true;
                }
            }
        }
        System.out.println(-1);
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<=n && y<=n) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y,cnt;
    Node(int x, int y, int cnt){
        this.x=x;
        this.y=y;
        this.cnt=cnt;
    }
}
​
​