[백준] 13913번 숨바꼭질 4 - 파이썬

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

13913번: 숨바꼭질 4

풀이

숨바꼭질 문제 시리즈의 4편이다. 다른점이 있다면 거쳐온 경로를 출력해야한다는것이다. move 리스트를 만들어서 새로운 점으로 도달하기전에 거쳐온 점을 저장해서 for문으로 출력해준다. 대신 값은 시작점부터 출력해야하기에 reveres를 해주었다.

# 13913 숨바꼭질
from collections import deque

def bfs():
    queue = deque()
    queue.append(s)
    distance[s] = 1
    while queue:
        x = queue.popleft()
        # 목표값에 도달
        if x == t:
            # 걸린 시간 출력
            print(distance[x]-1)
            path = [t]
            temp = t
            for i in range(distance[t]-1):
                path.append(move[temp])
                temp = move[temp]
            return path
        for nx in (x+1, x-1, 2*x):
            if 0 <= nx < 100001 and distance[nx] == 0:
                distance[nx] = distance[x] + 1
                # nx에 오기전에 거쳐온 x 저장
                move[nx] = x
                queue.append(nx)

s, t = map(int, input().split())
distance = [0] * 100001
move = [False] * 100001
path = bfs()
# 역순으로 출력
path.reverse()
for i in path:
    print(i, end=' ')

출력결과