13913_숨바꼭질

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

13913번: 숨바꼭질 4

 

 

 

숨바꼭질의 연장선 문제이다.

 

bfs를 통해서 카운트를 통해 몇초가 걸리는지 걸리는건 해볼 수 있다. 이때 0~100000까지의 배열을 만들어두고 해당하는 초를 새기면서 카운팅을 한다.

 

그렇다면 이 배열을 기록해나갈때 어느 점에서 나왔는지도 기록을 하면 쉽게 역추적을 할 수 있다. 이배열의 이름을 cnt라고 해보자

 

예를 들어

 

5 17인경우

 

5 10 9 18 17

5 4 8 16 17 

 

두가지가 나온다. ( bfs시 2*n을 먼저볼껀지 n+1을 먼저 탐색할껀지 차이)

 

그렇다면 5에서 10으로 갈때 cnt에 5에서 왔다라는 기록을 저장해주고 또 10에서 9로갈때 9에 10에서 왔다라는걸 기록해두면 역추적을 통해서 찾을 수 있다.

 

from collections import deque
n,k = map(int,input().split())
high = 100001
cnt = [ [-1 ,-1] for _ in range(high) ]
cnt[n][0] = 0
cnt[n][1] = n

def bfs(N):
    q = deque([N])
    while q:
        now = q.popleft()
        if now == k:
            return cnt[now][0]

        for next in (now*2,now+1,now-1):
            if 0 <= next < high and cnt[next][0] == -1:
                cnt[next][0] = cnt[now][0] + 1
                cnt[next][1] = now
                q.append(next)

bfs(n)
print(cnt[k][0])
tmp = k
result = []
while tmp != n:
    result.append(tmp)
    tmp = cnt[tmp][1]
result.append(n)
result.reverse()
print(*result)