[JAVA] 백준 16948번 : 데스 나이트

[16948번 : 데스 나이트] - Silver1

접근 : bfs

---

[ 문제 ]

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

# 예제 출력 1
4

---

[ Code ]

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Node {
        int r, c, cnt;

        public Node(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }

    static int n;
    static int min = Integer.MAX_VALUE;
    static int r1, c1, r2, c2;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dy = {-2, -2, 0, 0, 2, 2};
    static int[] dx = {-1, 1, -2, 2, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        visited = new boolean[n][n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        r1 = Integer.parseInt(st.nextToken());
        c1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());

        bfs(r1, c1);
        bw.write(String.valueOf(min == Integer.MAX_VALUE ? -1 : min));
        bw.close();
    }

    static void bfs(int r, int c) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(r, c, 0));
        visited[r][c] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();
            int curR = cur.r;
            int curC = cur.c;
            int curCnt = cur.cnt;

            if (curR == r2 && curC == c2) {
                min = Math.min(min, curCnt);
            }

            for (int i = 0; i < 6; i++) {
                int moveR = curR + dy[i];
                int moveC = curC + dx[i];

                if (isValid(moveR, moveC) && !visited[moveR][moveC]) {
                    visited[moveR][moveC] = true;
                    q.add(new Node(moveR, moveC, curCnt + 1));
                }
            }
        }
    }

    static boolean isValid(int moveR, int moveC) {
        return moveR >= 0 && moveC >= 0 && moveR < n && moveC < n;
    }
}

일반적인 bfs 풀이법이다.

1. 입력

- r1, c1부터 bfs 시작

 

2. bfs

- 큐 생성 후 r1, c1 추가

- 큐에 값이 없을 때까지 반복

- 현재 위치가 r2, c2면 최솟값인지 비교 후 값 갱신

- 총 6가지의 시나리오가 존재, 조건이 전부 참이면 현재 cnt에서 +1 후 큐에 추가

 

3. 출력

- min 값이 최초의 값인 Integer.MAX_VALUE라면 이동할 수 없는 경우이므로 -1 출력