[백준] 13913번 : 숨바꼭질4 - Python(파이썬)

문제

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

13913번: 숨바꼭질 4

 

풀이

• BFS : 자식 노드 하나씩 방문 : 주어진 값인지 확인 : que 이용
• 시간 : 깊이 하나씩 내려갈 때마다 +1
• 경로 : 이전 노드 (부모 노드) 하나씩 넣기 -> 거꾸로 출력

 

 

 

코드

from collections import deque

def path(x):
    arr = []
    temp = x
    for _ in range(dist_time[x]+1):
        arr.append(temp)
        temp = route[temp]
    print(' '.join(map(str,  arr[::-1])))

def bfs():
    q = deque()
    q.append(N)
    while q:
        x = q.popleft()
        if x == K: #동생 위치 도달
            print(dist_time[x]) #걸린 시간 출력
            path(x)
            return x
        for i in (x+1, x-1, 2*x): #이동하는 경우의 수 : 전진, 후진, 순간이동
            if 0<=i<=100000 and dist_time[i]==0:
                q.append(i)
                dist_time[i] = dist_time[x] + 1
                route[i] = x

N, K = map(int, input().split())
dist_time = [0]*100001
route = [0]*100001
bfs()