[백준] 12851 - 숨바꼭질2

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

12851번: 숨바꼭질 2

문제 한줄 이해

- 나와 동생의 위치가 주어지고 1초 뒤에 +1, -1 ,*2의 위치로 이동 할 수 있을 때 동생의 위치로 가는 빠른 시간과 빠른 시간의 경우의 수 구하기

생각난 풀이

1번째 방법: 현재 위치에서 1초뒤에 3가지 경우로 뻗어 나간다. 또한 뻗어 나간 그 위치에서도 각각 3가지 경우로 뻗어 나가는 상황을 생각하면 그래프 탐색이 떠올랐다!!

그래서 넓이우선탐색의 아이디어를 가져와서 각 위치에 도착했을 때 시간 값을 저장해주면서 작다면 갱신해주고 경우의 수도 계산해야하기 때문에 이전에 계산한 값과 같으면 경우의수 +=1 을 했다!

import sys
from collections import deque
n, k = map(int,sys.stdin.readline().split())

dp = [1e9] * 100001 # 각위치에 도작하기 전이므로 무한대로 설정
dp[n] = 0 # 현재 나의 위치는 0
que = deque()
que.append(n)
result = 1 #경우의 수는 1 why? 어떻게든 무조건 그 위치로 가는 경우는 한가지 이상!

while que:
    nown = que.popleft()
    
    #각 경우의 수!!
    for i in (nown+1,nown-1,2*nown):
        if i >= 0 and i <=100000:
        	#현재 시간 보다 작다면 갱신
            if dp[i] > dp[nown] + 1:
                if i ==k:
                    result = 1
                dp[i] = dp[nown]+1
                que.append(i)
            #현재 시간이랑 같다면 경우의수 +1
            elif dp[i] == dp[nown]+1:
                if i == k:
                    result +=1
                dp[i] = dp[nown]+1
                que.append(i)
                
print(dp[k])
print(result)