[알고리즘] 백준 13913 숨바꼭질4 / python

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

13913번: 숨바꼭질 4

 

✔ 풀이과정

bfs로 탐색을 할거니까 자식노드를 차례로 모두 방문한다. 방문하면서 K값인지 아닌지 확인한다. 

dist는 노드까지 가는데 몇초걸리는가?를 의미한다.

예를들어 5의 자식노드인 4, 6, 10의 dist는 1이므로 4, 6, 10까지 걸리는 최소 시간은 1인것이다.

dist 배열 👉 dist[현재 노드] = 걸리는 시간(초)

move 배열 👉 move[현재노드] = 이전 노드 (=부모노드)

move 배열에는 이전에 어떤 노드를 지나왔는지 기록되어 있으니까 그 경로를 탐색해서 배열에 넣고 거꾸로 출력해준다.

 

from collections import deque

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

def bfs():
    q = deque()
    q.append(N)
    while q:
        x = q.popleft()
        if x == K:
            print(dist[x])
            path(x)
            return x
        for i in (x+1, x-1, 2*x):
            if 0<=i<=100000 and dist[i]==0:
                q.append(i)
                dist[i] = dist[x] + 1
                move[i] = x

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