본문 바로가기

취준/백준

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

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

 

13913번: 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는

www.acmicpc.net

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)))