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

 

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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
    q=deque([n])
    while q:
        x=q.popleft()
        if x==k:
            return ans[x]
        #02
        for i in (x-1,x+1,2*x):
            if 0<=i<=10**5 and not ans[i]:
                ans[i]=ans[x]+1
                q.append(i)
#03
ans=[0]*(10**5+1)
n,k=map(int,input().split())
print(sol())

- #01 : deque를 사용한다. x에는 q의 제일 왼쪽 값을 추출하여 저장한다.

           만약 x의 값이 k와 같다면 정답이므로, ans[x]를 반환한다.

- #02 : 그렇지 않다면 i에는 숨바꼭질의 3가지 경우의 수를 모두 대입한다.

           만약 i가 조건의 범위이며, ans[i]도 0이라면 ans[i]에는 ans[x]에 1을 더한 값을 저장한다.

           q에는 i를 더하여 계속해서 나아가 최종적으로 x가 k가 될 때까지 반복한다.

- #03 :  ans에는 모두 0(False)를 넣어 #02의 if문을 가능하게 한다.

            결국 3가지 방법을 모두 시행해보며, 가장 빠르게 답에 도달할 수 있는

            bfs 방식을 사용하여 답을 얻을 수 있다.