[BOJ 13549] 숨바꼭질 3

Breadth First Search

[BOJ 13549] 숨바꼭질 3

문제

구조화

• BFS에서 풀었던 숨바꼭질 문제의 심화버전
• 모든 조건은 동일하나, 순간이동의 경우 0초 추가
• 단순히 조건을 걸어 해결하려 했으나, 시간초과 발생
  • 최단거리 문제이므로, 0초 이동 선택지는 최우선순위로 큐에 추가(appendleft)
  • 순간이동이 0초이므로, 초기화를 0으로 했다면 중복으로 인해 시간초과 발생
• 이후 -1로 초기화 후 진행하여 문제 해결

예제 시각화

해답

from collections import deque
import sys
input = sys.stdin.readline
n,k = map(int, input().split())
data = [-1 for i in range(100001)] # 최대 범위, 0으로 초기화한다면, 방문 가능 여부에서 순간 이동 시 중복으로 인해, 시간초과 발생. -1로 초기화
a=deque([n]) # 추가
data[n]=0
ans=[]
def bfs():
    while len(a):
        node = a.popleft()
        if node==k:
            ans.append(data[node])
        for nxt in (node-1, node+1, node*2): # 이동 가능 영역
            if nxt >= 0 and nxt <= len(data)-1:
                if nxt==node*2: # 순간이동을 진행했을 때
                    if data[nxt]==-1: # 방문하지 않은 경우
                        data[nxt] = data[node] # 0초 추가
                        a.appendleft(nxt) # 최단거리 문제이므로, 0초가 우선으로 큐에 추가
                else:
                    if data[nxt]==-1: # 일반적인 이동일 경우
                        data[nxt] = data[node]+1 # 1초 추가
                        a.append(nxt)
bfs()
print(min(ans))