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

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

문제

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만 출력합니다.

풀이

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

과정

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

한 위치에 도달할 수 있는 N개의 점이있다면 그 위치에 도달할 수 있는 경우는 N개의 점에 각각 도달할 수 있는 가짓수의 합과 같다. map[nr][nc] = (map[nr][nc] + map[temp.r][temp.c]) // 이를 10억 9로 나누어주어야 한다. 여기서 오버플로가 충분히 날 수 있으므로 2차원 배열의 자료형을long으로 선언했다.

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

처음 방문했을때만 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 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; } }

from http://skdltm117.tistory.com/41 by ccl(A) rewrite - 2021-12-12 17:02:06