[CLASS 4]백준 13549번 - 숨바꼭질 3

13549번 : 숨바꼭질 3

 

숨바꼭질 2에서 좀 힘들었던 경험이 있어서 3은 더 어렵지 않을까 걱정했지만 오히려 엄청 쉽게 풀 수 있었다. 이 문제에서 특이한 점은 순간이동은 시간을 소비하지 않는다는 것이다.

 

BFS를 수행하되 어떤 점에서 2배를 계속 하면서 큐에 한번에 다 추가해 주어야 한다. 그래야 큐 안에 시간이 2초 이상 차이나는 경로가 추가되지 않는다.

 

내 코드:

# dawitblog.tistory.com
from collections import deque

n,k = map(int,input().split())
if n >= k:
    print(n-k)
    exit()
limit = 2*k-n

q = deque([(n,0)])
visited = [False] * (limit+1)
visited[n] = True

while q:
    now, time = q.popleft()

    if now == k:
        print(time)
        exit()
	
    # 순간이동으로 갈 수 있는 곳 한번에 모두 추가
    tel = now * 2
    while 0 < tel <= limit and not visited[tel]:
        visited[tel] = True
        q.append((tel,time))
        tel *= 2
    
    b = now - 1
    if 0 <= b <= limit and not visited[b]:
        visited[b] = True
        q.append((b,time+1))
    
    f = now + 1
    if 0 <= f <= limit and not visited[f]:
        visited[f] = True
        q.append((f,time+1))