Java 백준 12851번 숨바꼭질2

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

---

문제

생각하기

---

• BFS 최적화문제이다.

• 숨바꼭질2 이전 문제를 먼저 풀어보는게 도움이 된다.

동작

이번에는 이전 문제인 숨바꼭질1에서 방법의 수도 출력하는 부분이 추가되었다.

방법의 수를 추가하는 것은 숨바꼭질 1을 풀어보신분이라면, 간단하다
그냥 수빈이와 동생이 만날때마다 count를 증가시키면된다.

내가 힘들었던 부분은 count값을 최솟값에 따라 갱신시켜주어야 하나 했는데,
애초에 que에서 계산되는 첫번째가 최단시간이기 때문에 그냥 증가시켜 주면 됬었다.

이전 숨바꼭질1에서는 if(next_time == K) { 조건에서 곧바로 return으로
종료시켰지만, 여기서는 count 증가도 있으니 지속해서 반복해야 한다.

그리고 최소시간보다 que에서 나온 위치의 시간이 더 클 경우
곧 바로 return; 으로 종료해주면 된다.

min_time = Integer.MAX_VALUE/16; 으로 초기화한 것은
그냥 Integer.MAX_VALUE로 설정하면 +를 해주었을 때, Integer범위를 넘어서
Integer.MIN_VALUE 값으로 넘어가버리기 때문에, 그냥 /16을 넣어서 설정해줬다.
(딱히 의미는 없고 그냥 최댓값으로 초기화 한거임)

그리고 한가지 예외케이스를 잊지 말자.
수빈이가 동생보다 더 앞에 있을 때,
수빈이는 순간이동을 앞으로 밖에 못한다. 그럼 뒤로가는 것은 -1 밖에 못한다는 얘기니까.
그리고 방법은 오직 1가지 밖에 없다.

		if(N >= K) {
			System.out.println(N-K);
            System.out.println(1);
			return;
		}

결과

코드

---

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, K;
    private static final int MAX = 100_001;
    private static final int INF = Integer.MAX_VALUE / 2;

    private static class Coordinate {
        int idx;
        int count;

        private Coordinate(int idx, int count) {
            this.idx = idx;
            this.count = count;
        }
    } // End of Coordinate class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        if (N >= K) {
            sb.append(N - K).append('\n').append(1);
            return sb.toString();
        }

        int[] ret = BFS();
        sb.append(ret[0]).append('\n').append(ret[1]);
        return sb.toString();
    } // End of solve()

    private static int[] BFS() {
        ArrayDeque<Coordinate> que = new ArrayDeque<>();
        int[] memo = new int[MAX];
        Arrays.fill(memo, INF);

        que.offer(new Coordinate(N, 0));
        memo[N] = 0;
        int minTime = INF;
        int ans = 0;

        while (!que.isEmpty()) {
            Coordinate cur = que.poll();

            // 가장 빠른 시간을 구하고, 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력
            if (cur.idx == K) {
                if (cur.count < minTime) {
                    minTime = cur.count;
                    ans = 1;
                } else {
                    ans++;
                }
                continue;
            }

            if (cur.idx + 1 < MAX && memo[cur.idx + 1] >= memo[cur.idx] + 1) {
                memo[cur.idx + 1] = memo[cur.idx] + 1;
                que.offer(new Coordinate(cur.idx + 1, memo[cur.idx + 1]));
            }

            if (cur.idx - 1 >= 0 && memo[cur.idx - 1] >= memo[cur.idx] + 1) {
                memo[cur.idx - 1] = memo[cur.idx] + 1;
                que.offer(new Coordinate(cur.idx - 1, memo[cur.idx - 1]));
            }

            // 순간이동
            if (cur.idx * 2 < MAX && memo[cur.idx * 2] >= memo[cur.idx] + 1) {
                memo[cur.idx * 2] = memo[cur.idx] + 1;
                que.offer(new Coordinate(cur.idx * 2, memo[cur.idx * 2]));
            }
        }

        return new int[]{minTime, ans};
    } // End of BFS()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
    } // End of input()
} // End of Main class