[백준] 11084번 - 나이트의 염탐 (java)

Baekjoon 11084 - 나이트의 염탐 (클릭 시 이동)

문제

Cube World와 Baekjoon World가 한창 전쟁 중일 때 있었던 일입니다. 이 두 나라는 r행 c열의 체스판으로 생각할 수 있고, Cube World의 수도는 (1,1)에, Baekjoon World의 수도는 (r,c)에 있습니다.

Cube World에서 Baekjoon World를 염탐하기 위해서 나이트를 보낸 적이 있습니다. 나이트는 가로 또는 세로로 두 칸 이동한 뒤, 수직한 방향으로 한 칸 이동할 수 있는 날렵한 염탐꾼입니다. 나이트는 최단거리로 이동했고, 그 거리와 가짓수를 미리 조사하여 들키지 않고 성공적으로 염탐하고 왔다고 전해집니다.

두 나라가 화해한 지금, Cube World의 국왕이 Baekjoon World의 국왕에게 이 이야기를 들려주자, 둘 모두 그 거리와 가짓수가 얼마였는지 궁금해졌습니다. 위대한 과학자인 당신이 이 문제를 해결해 주세요!

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	250	98	68	36.364%

입력

첫 줄에 행의 수 r과 열의 수 c가 공백을 사이에 두고 주어집니다. (1 ≤ r, c ≤ 400)

출력

첫 줄에 나이트가 이동한 거리와 그 가짓수를 공백을 사이에 두고 출력합니다. 가짓수가 너무 클 수 있으므로, 1 000 000 009로 나눈 나머지를 출력합니다.

만약 나이트가 국왕을 속였다면, 나이트의 목숨은 없기 때문에 None만 출력합니다.

풀이

1. bfs를 이용하여 0,0에서 N-1,M-1까지 이동한다.
2. BFS의 depth가 곧 나이트의 이동거리가 되며 해당 depth에서 도착지를 방문했다면 그 Depth를 모두 수행한 후의 (N-1,M-1)위치의 값이 가짓수이고 depth가 거리이다.
3. 어떤 임의의 nx,ny에 도착하려 할 때 여러 방향에서 그 위치에 도착할 수 있으므로 현재위치의 가짓수를 도착위치에 더해준다 ( (nx,ny) += (x,y) )
4. 처음 방문한 곳은 Queue에 넣어준다.

과정

1. 처음에는 그냥 BFS돌려서 N-1,M-1위치에 도착했을때 깊이만 구해주면 되는 문제라 생각했는데 10억으로 나누는 경우가 안생기지 않나? 라고 생각해서 다시 곰곰이 생각해보니 어리석었다는 것을 깨달았다.

2. 한 위치에 도달할 수 있는 N개의 점이있다면 그 위치에 도달할 수 있는 경우는 N개의 점에 각각 도달할 수 있는 가짓수의 합과 같다.

   map[nr][nc] = (map[nr][nc] + map[temp.r][temp.c]) // 이를 10억 9로 나누어주어야 한다.

   여기서 오버플로가 충분히 날 수 있으므로 2차원 배열의 자료형을long으로 선언했다.

3. 만약 입력값이 1,1이라면 나이트는 움직이지 않아도 된다. 별 생각없이 정답을 1,1이겠거니 하고 출력했다가 30분간 헛고생하면서 4번이나 틀렸다 .. (89%에서 계속 틀린다.)

4. 처음 방문했을때만 queue에 넣어줘도 되는 이유는 해당 depth에서 이동한 곳을 모두 반영한 뒤인 다음 depth에서 값을 가져다 쓰기 때문이다. queue의 특징 선입선출 때문

최종 소스코드

import java.io.*;
import java.util.*;

public class BJ_G3_11084_나이트의_염탐 {

    static int N, M;
    static int count = 0;    // 이동 가짓수
    static int distance = 0;    // 이동 거리

    // 나이트가 이동할 수 있는 8방향
    static int[][] deltas = { { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 }, { -2, 1 } };
    static long[][] map;
    static StringTokenizer st;

    static class RC {
        int r, c;

        public RC(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 입력이 1,1일 경우 이동은 하지 않고 가짓수는 1가지.
        if (N == 1 && M == 1) {
            System.out.println(0 + " " + 1);
            return;
        }

        map = new long[N][M];

        bfs();

        if (map[N - 1][M - 1] == 0)
            System.out.println("None");
        else {
            System.out.println(distance + " " + map[N - 1][M - 1]);
        }

    }

    static void bfs() {
        Queue<RC> queue = new LinkedList<>();
        queue.offer(new RC(0, 0));
        map[0][0] = 1;

        while (!queue.isEmpty()) {
            if (map[N - 1][M - 1] != 0)
                break;
            int size = queue.size();
            distance++;
            for (int step = 0; step < size; step++) {
                RC temp = queue.poll();

                for (int i = 0; i < 8; i++) {
                    int nr = temp.r + deltas[i][0];
                    int nc = temp.c + deltas[i][1];
                    if (isIn(nr, nc)) {
                        if (map[nr][nc] == 0)
                            queue.offer(new RC(nr, nc));
                map[nr][nc] = (map[nr][nc] + map[temp.r][temp.c]) %(long)(1e9 + 9);
                    }
                }
            }
        }
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }
}