BOJ 12851 숨바꼭질2(Pyhton 3)

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

개인적으로 숨바꼭질3 보다 어려운 문제같다.

S[x][0]은 가장 빠른 시간을 구하는 요소이고, S[x][1]은 경우의 수를 모두 구하는 요소로 다차원 배열을 만들었다.

x는 이전에 있던 좌표, nx는 수빈이가 이동하는 좌표이다.

if를 사용해서 수빈이가 처음 와본 좌표라면 경우의 수를 바로 이전에 있던 좌표의 경우의 수와 같게 해주고,(S[nx][1]=S[x][1])

elif를 이용해 수빈이가 이미 와본 좌표이지만, 도달하는 시간이 같다면 원래 그 좌표에 저장해두었던 경우의 수에 이전에 있던 좌표의 경우의 수를 더해주었다.(S[nx][1]+=S[x][1])

코드확인

from collections import deque
Max=100001
N,K=map(int,input().split())
S=[[Max,0] for _ in range(Max)]
S[N][0],S[N][1]=0,1
q=deque()
q.append(N)
while q:
    x=q.popleft()
    for nx in [x+1,x-1,2*x]:
        if 0<=nx<Max:
            if S[nx][0]==Max:
                q.append(nx)
                S[nx][0]=S[x][0]+1
                S[nx][1]=S[x][1]
            elif S[nx][0]==S[x][0]+1:
                S[nx][1]+=S[x][1]
print(S[K][0])
print(S[K][1])