[백준][Python][13913][BFS] 숨바꼭질 4

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

13913번: 숨바꼭질 4

2020/02/27 - [취준/백준] - [백준][Python][1697][BFS] 숨바꼭질

불러오는 중입니다...

BFS 문제다.

 

링크 걸어놓은 숨바꼭질 문제와 똑같은데, 어떻게 도착했는지를 출력해야 한다.

 

숨바꼭질 과 푸는 방법이 달라지는데, 차이점은 다음과 같다

1. 단순 방문확인으로 썼던 v 딕셔너리를 전 위치를 저장하는데 사용한다.
   1. 출발위치는 -1 로 하고
   2. v[현재] = 저번 위치
2. 그 후 while문을 돌며 v[도착] ->v[도착 1개전].... 순으로 -1이 나올때까지 history에 저장 후 출력한다.

import sys
from collections import deque

d = dict()
v = dict()
ret = 1000000000000

n,k = [int(i) for i in sys.stdin.readline().rstrip().split()]

history = []

def bfs(n,k):
    global ret,d

    q = deque()
    q.append(n)
    d[n] = 0
    v[n] = -1

    while q:
        l = q.popleft()
        if l in d:
            pass
        if l==k:
            break
        for loc in [l-1,l+1,2*l]:
            if loc not in d and 0<=loc <= 100001:
                d[loc] = d[l]+1
                v[loc] = l
                q.append(loc)


bfs(n,k)
print(d[k])
dv = v[k]
history.append(str(k))
while dv != -1:
    history.append(str(dv))
    dv = v[dv]
print(" ".join(reversed(history)))