백준 데스 나이트 (16948) - Java

 

 

---

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

16948번: 데스 나이트

---

[풀이]

그래프 PS 좀 해보신 분들은 문제 보시자 마자 페이커 빙의해서  풀었죠? 라고 말씀 하셨을 겁니다.

전형적인 BFS 문제이며 6방면 탐색을 통해서 답을 도출해 내시면 됩니다.

 

최소 이동 횟수는 즉 최단 경로를 의미 하므로 bfs로 해결할 수 있는 문제입니다.

정답 코드는 아래와 같습니다.

---

[Java]

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 Main{

    static int grid[][];
    static int dx[] = {-1, 1, -2, 2, -1,1};
    static int dy[] = {-2,-2, 0, 0, 2, 2};
    static boolean visited[][];
    static Pos end;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        grid = new int [size][size];
        visited = new boolean[size][size];

        StringTokenizer st = new StringTokenizer(br.readLine());
        Pos start = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        end = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        bfs(start);

    }

    public static void bfs(Pos start){
        Queue<Pos> queue = new LinkedList<>();
        queue.add(start);
        visited[start.y][start.x] = true;

        while(!queue.isEmpty()){
            Pos cur = queue.poll();

            for(int i=0; i<6; i++){
                int nextX = cur.x + dx[i];
                int nextY = cur.y + dy[i];

                if(nextX >=0 && nextX < grid.length && nextY >=0 && nextY < grid.length && !visited[nextY][nextX]){
                    if(nextX == end.x && nextY == end.y){
                        System.out.println(grid[cur.y][cur.x] + 1);
                        return;
                    }
                    visited[nextY][nextX] = true;
                    queue.add(new Pos(nextY,nextX));
                    grid[nextY][nextX] = grid[cur.y][cur.x] + 1;
                }
            }
        }
        System.out.println("-1");
    }

}

class Pos{
    int x;
    int y;

    public Pos(int y, int x){ this.x = x; this.y = y;};
}