BFS 백준 - 13913 [Python]

Problem)

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

13913번: 숨바꼭질 4

Solution)

• from[i] = 어디에서 왔는지
• 의미: from[i] -> i
• N에서 K를 가는 문제이기 때문에
• K부터 from을 통해서 N까지 가야한다.
• 즉, 역순으로 저장되기 때문에, 다시 역순으로 구하는 것이 필요하다.

Answer)

from collections import deque
import sys
MAX = 200000
sys.setrecursionlimit(MAX)
check = [False] * MAX
dist = [-1] * MAX
via = [-1] * MAX
n,m = map(int,input().split())
check[n] = True
dist[n] = 0
q = deque()
q.append(n)
while q:
    now = q.popleft()
    if now-1 >= 0 and not check[now-1]:
        q.append(now-1)
        check[now-1] = True
        dist[now-1] = dist[now] + 1
        via[now-1] = now
    if now+1 < MAX and not check[now+1]:
        q.append(now+1)
        check[now+1] = True
        dist[now+1] = dist[now] + 1
        via[now+1] = now
    if now*2 < MAX and not check[now*2]:
        q.append(now*2)
        check[now*2] = True
        dist[now*2] = dist[now] + 1
        via[now*2] = now
print(dist[m])
def go(n, m):
    if n != m:
        go(n, via[m])
    print(m, end=' ')
go(n, m)