[백준] [Python] 1697번 숨바꼭질 - BFS

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

Python

from collections import deque
import sys
n, k = map(int, sys.stdin.readline().split())
q = deque()
q.append(n)
visit = [0]*100001
visit[n] = 1
#첫번째 자리로 되돌아오는 경우를 방지하기 위해
#꼭 넣어주어야 함
    
while len(q) != 0:
    n = q.popleft()

    if n==k:
        break
    if 2*n < 100001 and visit[2*n] == 0:
        visit[2*n] = visit[n]+1
        q.append(2*n)
    if n+1 < 100001 and visit[n+1] == 0:
        visit[n+1] = visit[n]+1
        q.append(n+1)
    if n-1 >= 0 and visit[n-1] == 0:
        visit[n-1] = visit[n]+1
        q.append(n-1)
    #print(q)
print(visit[k]-1)

 

 

 

+) [100000]*100001 은 당연히 메모리 초과