[알고리즘] 백준 12851 파이썬 - 숨바꼭질2

 

12851번: 숨바꼭질 2

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

문제풀이

from collections import deque
def sol():
	#01
    global cnt
    q=deque([n])
    while q:
    	#02
        x=q.popleft()
        if x==k:
            cnt+=1
        #03
        for i in (x-1,x+1,2*x):
            if 0<=i<=10**5:
                if ans[i]==-1 or ans[i]==ans[x]+1:
                    ans[i]=ans[x]+1
                    q.append(i)
#04
cnt=0
ans=[-1]*(10**5+1)
n,k=map(int,input().split())
ans[n]=0
sol()
print(ans[k])
print(cnt)

- #01 : cnt를 sol()에서도 사용할 수 있게 해준 후 q에 초기값으로 n을 넣어준다.

- #02 : x에는 q의 맨 왼쪽 값을 pop하여 저장한다. 만약 x가 k와 같다면 cnt에 1을 더해준다.

- #03 : i에는 문제에서 제공한 3가지 방법을 넣어준다.

           조건문을 통해 최대값을 넘지 않으며 ans가 초기값인 -1이거나

           ans[i]가 ans[x]와 1만큼 차이나는 즉 최단 시간의 요건을 만족하는 경우이면

           ans[i]에 ans[x]+1을 저장 후 q에 i를 추가해준다.

- #04 : sol()에서 사용할 cnt, ans 등을 입력받고, 최종적으로 가장 빠른 시간과 횟수를 출력한다.