13549: 숨바꼭질 3

import sys
from collections import deque

def bfs(N, K):
    queue = deque([]); queue.append(N)
    visit[N] = 0

    while queue:
        curr = queue.popleft()

        if curr == K:
            print(visit[curr])
            return

        if 0 <= curr*2 <= 100000 and visit[curr * 2] == -1: #순간이동은 0초 걸리기 때문에 우선 순위가 가장 높아야함
            queue.appendleft(curr * 2); visit[curr*2] = visit[curr]
        if 0 <= curr-1 <= 100000 and visit[curr - 1] == -1:
            queue.append(curr - 1); visit[curr-1] = visit[curr] + 1
        if 0 <= curr+1 <= 100000 and visit[curr + 1] == -1:
            queue.append(curr + 1); visit[curr+1] = visit[curr] + 1
        

         
N, K = map(int, input().split(' '))

visit = [-1] * (100000+1) #순간이동은 0초 걸리기 때문에 초기화를 0이 아닌 -1로 해줘야함
bfs(N, K)

• 최단 시간 -> 최단 경로 -> bfs
• X*2는 X+1, X-1과 달리 0초 걸리기 때문에, 우선 순위를 더 높게 주어야함
• 우선 순위를 높게 주기 위해 X*2를 하여 도착한 위치는 queue의 head쪽에 값을 넣음 (나머지 X+1, X-1은 queue의 tail쪽에 넣음)
• visit list를 초기화 할 때, X*2의 경우는 0초가 걸리기 때문에 0이 아닌 -1로 초기화를 해줘야함
• (아직도 의문인게 if문 순서에 따라 가끔 채점이 틀릴 때도 있는데 왜 그러는지 이유를 잘 모르겠다)