1697_숨바꼭질

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

1697번: 숨바꼭질

 

bfs를 이용하면 풀면 된다!

 

처음엔 단순하게 que에 현재 점을 추가해 가면서 하려 했는데 수가 너무 커지거나 해서 시간초과나 메모리 초과가 계속해서 났다. 

 

한번 들렀던 점은 그때가 최소이기에 두번 들리지 않고, 또한 값이 0 < x < 100000으로 정해져 있기때문에 이를 제한해두고 문제를 푸니 풀렸다.

 

 

from collections import deque
n,m = map(int,input().split())


q = deque([n])
dp= [ 0 for _ in range(100001)]

while q:
    x = q.popleft()
    if x == m :
        print(dp[x])
        break

    for nx in (x-1,x+1,2*x):
        if 0 <= nx <= 100000 and not dp[nx]:
            dp[nx] = dp[x] +1
            q.append(nx)