[백준] 숨바꼭질 2

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

12851번: 숨바꼭질 2

bfs를 이용하는 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 

0<= N, K <= 100,000의 범위안에서 N이 K로 이동해야 합니다. 이 때, N은 N-1, N+1, N*2의 위치로 1의 시간동안 이동할 수 있습니다. 이 때, N이 K로 도달하기 위한 최소 시간과, 그러한 경로의 갯수를 구해야 하는 문제입니다. 

 

https://life318.tistory.com/103

[백준] 숨바꼭질 3 — 우석블로그

문제와 유사합니다.

 

<Solution>

우선 N-1, N+1, N*2로 이동하는데는 모두 같은 1이라는 시간이 걸리므로 bfs를 활용하면 괜찮겠다 라는 생각을 할 수 있습니다.

 

그러면 전체적인 아이디어는 "bfs를 활용하자" 로 두고, 이제 우리가 추가적으로 최단 시간 말고 구해야 하는 정보(이런 최단경로의 갯수)들을 어떻게 얻을 수 있는지를 생각해 봅시다.

 

1. 최단 경로의 갯수

bfs를 통해 처음으로 K에 도달하는 경우가 나오게 되면 그 때의 시간이 최단 시간인 것은 자명합니다. 그리고 이후에 q에 남아 있는 것들은 같은 시간 일 수도 있고, +1이 된 값일 수도 있습니다.

 

따라서 q안에 들어가는 정보를 [위치, 시간] 으로 두고, 처음으로 K를 만날 때의 시간과 일치 하는 경우들만 q에서 추가적으로 제거하면서 위치가 K와 일치하는지를 체크하고, 만약 시간이 +1이 되는 지점이 되면, break시키면 됩니다. 

 

2. 가지치기

단순하게 bfs를 하게 되면 필요없는 searching이 많은 것을 알 수 있습니다. 

간단하게 예시를 들면, 

 

N=3인 상황을 생각해봅시다. 

 

time = 0

3

 

time = 1

3 -> 4,2,6

 

time = 2

4-> 5, 3, 8

2-> 3, 1, 4

6-> 7, 5, 12

 

각각 시간에 따라 bfs의 진행과정에서 등장하는 정보들을 적어 두었습니다. 시간이 0인 경우 3, 시간이 1인 경우에는 시간이 0일 때의 3으로 부터 유도되는 4,2,6이 등장하고, 이후의 과정들 또한 마찬가지 입니다. 

 

이 때 3은 시간 0만에 도달이 가능하지만 이후에 time=2인 곳에도 두번 등장하게 됩니다. 이렇게 도달한 3을 통한 경로는 최단경로가 절대 될수 없으므로 searching할 필요가 없습니다. 

 

따라서 위 상황에서 highlight된 부분들은 모두 불필요합니다. 

 

따라서 time_memory array를 두어 불필요한 가지치기를 시간정보를 담아두고, 대소 비교를 통해 제거할 수 있습니다. 

추가적으로, 위에서 time=2인 경우 4에서 유도되는 5, 6에서 유도되는 5는 둘다 처리를 해 주어야 하는 것에 유의하여야 합니다. 

우리는 모든 최단 경로의 갯수를 구해야 하기 때문에 위의 경우에는 둘을 거치는 경로가 다르기 때문에 count해주어야 하기에 생략을 하면 안됩니다. 

 

실제 구현은 아래와 같습니다.

import sys
from collections import deque

N, K = list(map(int, sys.stdin.readline().rstrip().split()))
# range 0 ≤ N,K ≤ 100,000
# bfs
q = deque([[N,0]]) # position, time

stop_time = int(2e9)
path_count = 0
time_memory = [int(2e9)] * (100_000 + 1)
# initial time_memory
time_memory[N] = 0

while(q):
    position, time = q.popleft()
    
    # init stop_time and count path
    if position == K:
        if stop_time > time:
            stop_time = time
        path_count +=1
            
    if time > stop_time:
        break
    
    if position + 1 <= 100_000 and time_memory[position+1] >= time+1:
        q.append([position+1, time + 1])
        time_memory[position+1] = time+1
    if position - 1 >= 0 and time_memory[position-1] >= time+1:
        q.append([position-1, time + 1])
        time_memory[position-1] = time+1
    if position * 2 <= 100_000 and time_memory[position*2] >= time+1:
        q.append([position * 2, time + 1])
        time_memory[position*2] = time+1

print(stop_time)
print(path_count)