BOJ#12851 숨바꼭질 2

BOJ#12851 숨바꼭질 2

* 문제

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

* 풀이

쉬운 문제인데 푸는데 고생을 좀 했습니다.

일단은 1697 숨바꼭질 문제와 동일한데..

동생을 찾는 가장 빠른 시간을 출력하는 것과

가장 빠른 시간으로 찾는 방법의 개수까지 출력해야 합니다.

헷갈리지 말아야 할 것은 가장 빠른 시간으로 찾는 '경로'가 아니라 '방법'의 개수 입니다.

즉, 입력 데이터가 1 10일 때

가장 빠른 경로는 1 -> 2 -> 4 -> 5 -> 10 이지만

방법으로 따지면 아래와 같이 2가지가 있습니다.

1 -> 2(+1) -> 4(*2) -> 5(+1) -> 10(*2)

1 -> 2(*2) -> 4(*2) -> 5(+1) -> 10(*2)

따라서 방법의 개수를 구하려면 큐에 정점이 중복 입력 될 수 있도록 해야합니다.

즉, 각 정점을 큐에 넣을 때

발견된 상태에 따라 큐에 넣는 것이 아니라(discovered)

방문된 상태에 따라 큐에 넣어야 합니다.(visited)

-> 방문된 정점은 큐에 넣지 않는다. 발견되었으나 방문되지 않은 정점은 큐에 넣는다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%2312851_CatchTheCow2/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * BOJ#12851 숨바꼭질2
 * https://www.acmicpc.net/problem/12851
 */

public class Main {

    static final int MIN_VALUE = 0;
    static final int MAX_VALUE = 100000;
    static boolean[] visited = new boolean[100001];
    static int ans = 1000000000;

    public static void main(String[] args) throws IOException {

        int N; // 수빈이 위치 0 <= N <= 100,000
        int K; // 동생의 위치 0 <= K <= 100,000
        HashMap<Integer, Integer> map = new HashMap<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        bfs(N, K, map);
        System.out.println(ans);
        System.out.println(map.get(ans));
    }

    static void bfs(int N, int K, HashMap<Integer, Integer> map) {

        int time = -1;
        int cnt = 0;
        Queue<Integer> q = new LinkedList<>();

        q.add(N);

        while (!q.isEmpty()) {

            time++;

            int size = q.size();
            for (int i = 0; i < size; i++) {

                int u = q.poll();
                visited[u] = true;

                if (u == K) {

                    if (ans >= time) {
                        ans = time;

                        if (map.get(ans) == null) {

                            map.put(ans, 1);
                        } else {

                            map.put(ans, map.get(ans) + 1);
                        }
                    }
                }

                if (u > MIN_VALUE && !visited[u - 1]) {

                    q.add(u - 1);
                }

                if (u < MAX_VALUE && !visited[u + 1]) {

                    q.add(u + 1);
                }

                if (u * 2 <= MAX_VALUE && !visited[u * 2]) {

                    q.add(u * 2);
                }
            }
        }
    }
}