[백준 / 13913] 숨바꼭질 4 - Python

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

13913번: 숨바꼭질 4

 

<풀이>

기존 숨바꼭질 문제에서 변형해왔다.

 

모든 경로를 list에 담아서 전달해줬더니 메모리 초과가 나온다.

따라서 해당 경로의 이전 값을 저장하는 리스트를 만들어줘서 역추적 했다.

 

2022.04.06 - [# Coding/# 백준] - [백준 / 1697] 숨바꼭질 - Python

[백준 / 1697] 숨바꼭질 - Python

 

 

<전체 코드>

 

from collections import deque

n, k = map(int, input().split())
graph = [float('inf')] * 200000
way = [-1] * 200000
queue = deque([[n, 0]])
graph[n] = 0

while queue:
    now, time = queue.popleft()
    if graph[now] < time:
        continue
    if now < k:
        nexts = [now-1, now+1, now*2]
    else:
        nexts = [now-1]
    for next in nexts:
        if next == -1:
            continue
        if graph[next] > time+1:
            graph[next] = time+1
            way[next] = now
            queue.append([next, time+1])

print(graph[k])
answer = str(k)
now = k
while now != n:
    answer = str(way[now]) + ' ' + answer
    now = way[now]
print(answer)