13549번 숨바꼭질3 백준 파이썬

문제:www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

import sys
from collections import deque
def solve(visited,n,k):
    queue=deque()
    queue.append(n)
    travel[n]=True
    while queue:
        x=queue.popleft()
        if x==k:
            print(visited[x])
            return
        nx=set() #중복제거
        nx.add(x+1)
        nx.add(x-1)
        nx.add(x*2)
        for t in nx:
            if 0<=t<100001 and visited[t]==0:
                if t==x*2 and not travel[t]:
                    visited[t]=visited[x]
                    travel[t]=True 
                   queue.appendleft(t) #우선순위 부여
                else:
                    if visited[t]==0 and not travel[t]:
                        visited[t]=visited[x]+1
                        travel[t]=True
                        queue.append(t)
 
n,k=map(int,input().split())
visited=[0]*100001
travel=[False]*100001
solve(visited,n,k)

이 문제의 경우는 숨바꼭질에서 2배 이동한 경우는 시간이 0초라는 조건이 붙혀진 문제이다.

나는 이문제를 풀기위해 2배이동하는 것을 우선순위를 두기 위해 deque에서 appendleft를 했다. 이러면 2배로 이동한 좌표들이 먼저 확인되기 때문에 가장 빠른 시간을 추적할 수가 있다. 또한 x-1,x+1,x*2의 값이 겹치는 것을 우려하여 set()에 중복제거를 한 후 반복문을 돌렸다.