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

12851번 : 숨바꼭질 2

 

 

숨바꼭질 1 문제를 푼 기억이 있어서 2도 엄청 쉽게 풀 수 있을 줄 알았는데 착각이었다.. 1과의 차이점은 최단시간으로 가는 서로 다른 최단경로가 몇가지 있는지까지 찾아야 하는 것인데, 이게 생각보다 쉽게 찾아지지가 않았다.

 

내 코드:

# dawitblog.tistory.com
from collections import deque
n, k = map(int,input().split())
if n >= k:
    print(n-k,1,sep='\n')
    exit()

check = [[-1,0] for _ in range(100001)]
q = deque()
q.append(n)
check[n] = [0,1]

while q:
    now = q.popleft()

    for new in (now-1,now+1,now*2):
        if 0<= new <= 100000:
            if check[new][0] == -1:
                check[new][0] = check[now][0] + 1
                check[new][1] = check[now][1]
                q.append(new)
            
            elif check[new][0] == check[now][0] + 1:
                check[new][1] += check[now][1]

print(check[k][0],check[k][1],sep='\n')

 

check라는 배열에 10만개의 [-1,0]을 넣는다. check[a][0]은 a에 도달하는데 걸린 시간(한 번도 도달하지 못했다면 -1), check[a][1]은 a에 도달하는 경우의 수가 저장된다.

 

어떤 값 a에 처음 도달했다면 check[a][0]은 -1일 것이다. 이때 check[a][0]에는 이전 값의 시간 +1을 저장해 주고, check[a][1]은 이전 값의 경우의 수를 그대로 가져가면 된다.

 

만약 a에 다른 방법으로 다시 도착했다면, 최단시간이라는 가정 하에 check[a][1]에 이전 경우의 수만 더해주면 된다.