[BOJ] 숨바꼭질 3

---

코드

import sys
from collections import deque
input = sys.stdin.readline


def bfs():
    global ans
    q = deque()
    q.append((n, 0))
    while q:
        cur, time = q.popleft()
        visited[cur] = 1
            
        if cur == k:
            print(time)
            break

        for nx in (cur-1, cur+1, cur*2):
            if 0 <= nx <= 100000 and not visited[nx]:
                if nx // 2 == cur:    # 순간이동인 경우 큐의 맨 앞에 추가
                    q.appendleft((nx, time))
                else:
                    q.append((nx, time+1))
        
n, k = map(int, input().split())
visited = [0]*100001
bfs()

결과

풀이 방법

• BFS를 활용하는 문제이다. 단 가중치가 0-1인 0-1 BFS이다.
• 한 칸씩 움직일 때 1초가 소요되는것과 달리 순간이동할 때는 시간이 소요되지 않으므로, 순간이동의 경우 큐의 맨 앞에 추가해야 한다. 최소시간을 구해야 하므로 소요시간이 작은 것을 먼저 방문해야 하기 때문이다.
• 소요시간이 작은 것을 먼저 방문하므로, 방문한 위치는 visited = True로 표시해주면 된다.
• 파이썬 deque 라이브러리는 appendleft() 함수를 지원하여 큐의 맨 앞에 데이터를 추가할 수 있다.

---