[백준] 12851번 - 숨바꼭질2

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

12851번: 숨바꼭질 2

 

문제 접근

가장 빠른 시간으로 접근에서 가장 빠른 = 최단 거리로 생각하고 BFS를 떠올렸다!

이 문제에서는 가장 빠른 시간 뿐만 아니라 방법의 수 까지 생각해주어야 한다..!

걸리는 시간은 visited 배열로 해결해주었고, 방법의 수는 cnt라는 배열을 따로 두어 경우의 수의 합을 이용해서 구현해주었다.

 

 

풀이

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

public class Main {

    public static final int MAX = 100_000;
    public static int N, K, time, res;

    public static int[] visited;
    public static int[] cnt;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        visited = new int[MAX + 1];
        cnt = new int[MAX + 1];

        cnt[N] = 1;
        visited[N] = 1;

        if (N == K) {
            sb = new StringBuilder();
            sb.append(0 + "\n");
            sb.append(1);
            bw.write(sb.toString());
            bw.close();
            br.close();
            return;
        }

        bfs();

        sb = new StringBuilder();
        sb.append(visited[K] - 1 + "\n");
        sb.append(cnt[K] + "\n");
        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    // 가장 빠른 : BFS
    public static void bfs() {

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (int value : new int[]{cur - 1, cur + 1, cur * 2}) {
                if (value < 0 || value > MAX) {
                    continue;
                }

                if (visited[value] == 0) { // 한번도 방문하지 않은 경우
                    visited[value] = visited[cur] + 1; // time 추가
                    queue.offer(value);
                    cnt[value] += cnt[cur]; // value나올때까지의 횟수 추가
                } else if (visited[value] == visited[cur] + 1) { // 방문을 했는데 가장 빠른 경우인 경우
                    cnt[value] += cnt[cur];
                }
            }
        }
    }
}

 

한가지 중요한 점은

예시처럼 17을 이미 방문한 상황이면 visited[17]이 0이 아닌 다른 수로 값이 바뀌어있다. 여기서 주의해야할 점은 17을 방문하는 경우는 더있을 수 있다는 점이다. 즉, 만약에 기존에 17을 방문하는 경우와 걸리는 시간이 같은 경우에는 방법의 수를 더해주어야 한다.

 

else if (visited[value] == visited[cur] + 1) { // 방문을 했는데 가장 빠른 경우인 경우
     cnt[value] += cnt[cur];
}

이 로직이 제일 중요하다!

 

반례 - 같은 경우도 생각해주어야 한다.

if (N == K) {
            sb = new StringBuilder();
            sb.append(0 + "\n");
            sb.append(1);
            bw.write(sb.toString());
            bw.close();
            br.close();
            return;
        }

 

어렵다 어려워..! 그렇지만 포기하지 않는다!