[백준 알고리즘] 12851번 숨박꼭질 2 (Java) 문제 풀이

문제

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

12851번: 숨바꼭질 2

어떻게 풀 것인가?

BFS에서 중복 방문에 대한 체크를 삭제 해야 접근이 가능했던 문제였다.

중복 방문을 허용하게 된다면, 여러가지의 경우수 접근 자체가 불가능하다.

최단 시간을 구하라는 점은 숨박꼭질1번 문제와 똑같지만, 이번에는 최단 시간에 만나는 모든 경우를 구해야 한다.

 

즉, 생각해보자.

 

1. 방문 탐색을 하면서 시간을 계산해야한다.

2. 또한 경우의 수를 계산해야한다.

 

위 2가지의 과정이 이루어져야한다.

 

또한 중복에 대한 문제에서도 생각해야할 점이 있다.

 

이전 방문 시간이 현재 방문 시간보다 빠른 경우 와 이전 방문 시간이 현재 방문 시간보다 느린 경우는 제외하고 생각해도된다.

그렇다면 이전 방문 시간이 현재 방문 시간과 같은 경우에 대해서만 생각하면 문제는 풀리게 된다.

(아래 블로그 참고)

 

풀면서 놓쳤던점

처음에 풀었던 숨박꼭질 문제에서 코드를 가져와 풀다보니 계속 헤매였다. 

 

이 문제를 통해 얻어갈 것

문제에 대한 깊은 이해화 BFS의 활용에 대해서 공부할 수 있었다.

 

내 코드 

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

// 백준알고리즘 12851번 숨박꼭질 2

public class Main {
    static int me, brother;
    static int[] time = new int[100001];
    static int minTime = 987654321;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        me = Integer.parseInt(st.nextToken());
        brother = Integer.parseInt(st.nextToken());

        if (me >= brother) {
            System.out.println((me - brother) + "\n1");
            return;
        }

        BFS();

        System.out.println(minTime + "\n" + count);
    }

    private static void BFS() {
        Queue<Integer> que = new LinkedList<>();
        que.add(me);
        time[me] = 1;
        while (!que.isEmpty()) {
            int now = que.poll();
            if (minTime < time[now]) return;

            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 0) next = now + 1;
                else if (i == 1) next = now - 1;
                else next = now * 2;
                if (next == brother) {
                    minTime = time[now];
                    count++;
                }
                if (next < 0 || next > 100000) continue;

                if (time[next] == 0 || time[next] == time[now] + 1) {
                    que.add(next);
                    time[next] = time[now] + 1;
                }
            }
        }
    }
}

 

참고

https://bcp0109.tistory.com/154

백준 12851번. 숨바꼭질 2 (Java)