[백준 16948, Java] 데스 나이트

문제

www.acmicpc.net/problem/16948

16948번: 데스 나이트

풀이

 이건 진짜 기본 bfs!

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Knight{
    int x, y, count;
    Knight(int x, int y, int count){
        this.x = x;
        this.y = y;
        this.count = count;
    }
}
public class Main {
    static int[] dx = {-2,-2,0,0,2,2};
    static int[] dy = {-1,1,-2,2,-1,1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine().trim());

        st = new StringTokenizer(br.readLine()," ");
        int fromX = Integer.parseInt(st.nextToken());
        int fromY = Integer.parseInt(st.nextToken());
        int toX = Integer.parseInt(st.nextToken());
        int toY = Integer.parseInt(st.nextToken());

        int result = minDistance(n,fromX,fromY,toX,toY);
        bw.write(String.valueOf(result));
        bw.flush();
    }

    static int minDistance(int n, int fromX, int fromY, int toX, int toY){
        Queue<Knight> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];

        queue.add(new Knight(fromX,fromY,0));
        visited[fromX][fromY] = true;

        while (!queue.isEmpty()){
            Knight currentKnight = queue.poll();
            if(currentKnight.x == toX && currentKnight.y == toY){
                return currentKnight.count;
            }
            else{
                for(int d=0; d<6; d++){
                    int nx = currentKnight.x + dx[d];
                    int ny = currentKnight.y + dy[d];
                    int nc = currentKnight.count + 1;

                    if(nx>=0 && nx<n && ny>=0 && ny<n){
                        if(!visited[nx][ny]){
                            queue.add(new Knight(nx,ny,nc));
                            visited[nx][ny] =true;
                        }
                    }
                }
            }

        }
        return -1;

    }
}