[파이썬] 백준 13913 : 숨바꼭질 4

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

13913번: 숨바꼭질 4

from collections import deque

 

INF = 100000

N, K= map(int, input().split())

dist = [0]*(INF+1)

path = [0]*(INF+1)

 

 

def solve_bfs():

    q = deque()

    q.append(N)

    while q:

        x = q.popleft()

        if x == K:

            print(dist[x])

            p = []

            while x != N:

                p.append(x)

                x = path[x]

            p.append(N)

            p.reverse()

            print(' '.join(map(str, p)))

            return

        for nx in (x*2,x-1, x+1):

            if 0 <= nx <= INF and not dist[nx]:

                dist[nx] = dist[x]+1

                path[nx] = x

                q.append(nx)

 

 

solve_bfs()

 

path는 이전 점을 저장해놓는 리스트

dist는 이제껏 몇 번 이동했는지를 저장해놓는 리스트

p는 경로 저장 리스트

 

참고로 for nx in (x*2,x-1,x+1)에서 x*2,x-1,x+1에 따라 들리는 점 순서 바뀔 수도 있다.

 

피드백은 언제나 환영입니다:)