[ 문제 ]

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

[ 알고리즘 유형 ]

그래프 이론
자료 구조
그래프 탐색
너비 우선 탐색
다익스트라
0-1 너비 우선 탐색

[ 정답 코드 ]

BFS

from collections import deque
MAX = 100001
check = [False] * MAX
dist = [-1] * MAX

n,k = map(int, input().split())
q = deque()
q.append(n)
check[n] = True
dist[n] = 0

while q:
    now = q.popleft()
    if now*2 <= MAX and check[now*2] == False:  # 순간이동
        q.appendleft(now*2)
        check[now*2] = True
        dist[now*2] = dist[now]
    if now + 1 <= MAX and check[now+1] == False: # x+1이동
        q.append(now+1)
        check[now+1] = True
        dist[now+1] = dist[now] + 1
    if now - 1 >= 0 and check[now-1] == False: # x-1이동
        q.append(now-1)
        check[now-1] = True
        dist[now-1] = dist[now] + 1
print(dist[k])

[ 풀이 방법 ]

숨바꼭질 문제에서는 모든 가중치가 1이였다.
그러나 숨바꼭질3에서는 순간이동은 0초, 이동은 1초가 걸린다.

즉,
걷기 : x+1 또는 x-1 (1초)
순간이동 : 2*x (0초)

단계별로 이루어진다는 점을 고려하여 큐를 2개로 나눠 구현하면 된다.

양방향 큐인 deque을 활용하여 큐 2개를 별도로 만들지 않고, 순간이동할 경우 맨 앞에 값 추가, 이동한 값은 뒤에 값을 추가했다.

[ 풀이과정 이슈 ]

런타임에러 발생
MAX = 100000

=> 수정
MAX = 100001

MAX값 할당 실수 ^^;