백준 16948 - 데스나이트(그래프) 자바 JAVA

https://www.acmicpc.net/problem/16948

16948번: 데스 나이트

 

문제분석

최소이동 횟수를 구하는 문제이기 때문에 BFS로 풀 수 있다.

x,y 좌표를 Queue에 넣어야하기 때문에 Node라는 Class가 필요하다.

 

풀이

1. BFS로 탐색하면서 해당 칸까지의 최단거리를 방문 배열에 저장한다.

2. Queue가 빌 때까지 반복한다.

3. r2,c2 방문 배열 값을 출력한다. 

 

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class p16948_데스나이트 {
    static int N;   //체스판의 크기
    static int r1;
    static int c1;
    static int r2;
    static int c2;
    static int[][] visited;       //방문 배열
    static int[][] map;             //체스판 배열
    static int[] X = {-2,-2,0,0,2,2};
    static int[] Y = {-1,1,-2,2,-1,1};

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        N = scan.nextInt();
        r1 = scan.nextInt();
        c1 = scan.nextInt();
        r2 = scan.nextInt();
        c2 = scan.nextInt();

        map = new int[N][N];
        visited = new int[N][N];
        for(int i = 0; i < N; i++){     //방문배열 초기화
            for(int j = 0; j < N; j++){
                visited[i][j] = -1;
            }
        }

        BFS(r1,c1);

        System.out.print(visited[r2][c2]);
    }

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

    private static void BFS(int r1, int c1) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(r1,c1));
        visited[r1][c1]++;
        while (!queue.isEmpty()){
            Node now_node = queue.poll();
            int nowX = now_node.x;
            int nowY = now_node.y;
            if(nowX == r2 && nowY == c2){
                break;
            }
            for(int i = 0; i < 6; i++){
                int nextX = nowX + X[i];
                int nextY = nowY + Y[i];

                if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= N){
                    continue;
                }

                if(visited[nextX][nextY] == -1){
                    queue.add(new Node(nextX,nextY));
                    visited[nextX][nextY] = visited[nowX][nowY] + 1;
                }
            }
        }
    }
}