BOJ 13549 숨바꼭질3(Python 3)

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

숨바꼭질1과 비슷해 보이지만 0초 후에 2*X의 위치로 이동하게 된다는 내용으로 조건이 변경된 문제이다.

이 경우에는 X-1,X+1을 먼저 하는 것보다는 2*X로 이동할 수 있으면 전부 2*X로 이동시키고, 그다음 X-1,X+1로 이동시키면 된다.

코드1은 2*X로 이동시킬 때 collections.deque에 있는 명령어인 appendleft를 사용하였는데 appendleft는 큐의 맨 왼쪽으로 넣는 명령어이기 떄문에 bfs와 똑같이 popleft를 이용하면 된다.

코드2는 큐 자체를 덱이 아닌 리스트로 만든다음. heapq의 명령어인 heappush,heappop을 이용하여 bfs를 만들었다.

heapq는 값을 계속 정렬해서 저장하기 때문에 배열을 큐에 저장할때 꼭 [시간,좌표] 로 값을 저장해야한다.

(최단 시간을 구하는 것이기 때문에 시간을 기준으로 정렬 해야함)

C언어에 나온 우선 순위 큐와 작동방식은 똑같다.

코드1 확인

from collections import deque
N,K=map(int,input().split())
Max=10**5+1
D=[-1]*Max
D[N]=0
q=deque([N])
while q:
    x=q.popleft()
    for nx in [2*x,x+1,x-1]:
        if 0<=nx<Max and D[nx]==-1:
            if nx==2*x:
                q.appendleft(nx)
                D[nx]=D[x]
            else:
                q.append(nx)
                D[nx]=D[x]+1
print(D[K])

코드2 확인

from heapq import *
N,K=map(int,input().split())
Max=10**5+1
D=[-1]*Max
D[N]=0
q=[]
heappush(q,[0,N])
while q:
    t,x=heappop(q)
    for nx in [2*x,x+1,x-1]:
        if 0<=nx<Max and D[nx]==-1:
            if nx==x*2:
                heappush(q,[t,nx])
                D[nx]=t
            else:
                heappush(q,[t+1,nx])
                D[nx]=t+1
print(D[K])