숨바꼭질 4

백준 13913

수빈이가 동생을 찾는 가장 빠른 시간과 경로 구하기.

• 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
• 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
• 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
• 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
• 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

입출력

입력	출력
5 17	4 5 10 9 18 17
5 17	4 5 4 8 16 17

---

접근 방식

: 경로를 어떻게 출력해야할 지?

알게된 점

해당 경로를 방문하기 바로 전 방문한 지점을 저장하는 배열이 필요
path[a] = b 이면 b지점에서 바로 a지점을 방문했다는 뜻.

x가 n이 될 때까지 path[x]를 ans 리스트에 담는다. 이후 ans 리스트를 reverse함수로 거꾸로 값을 정렬하고 값만 출력한다.

코드

from collections import deque

def bfs(n, k, visited, path):
    q = deque()
    q.append(n)

    while q:
        x = q.popleft()

        if x == k:
            print(visited[x]) 
            
            ans = []
            while True:
                ans.append(x)
                if x == n:
                    break
                x = path[x]
                
            ans.reverse()
            print(*ans)
            return

        for nx in (x-1, x+1, x*2):
            if 0<=nx<=100000 and visited[nx]==0:
                visited[nx] = visited[x] + 1
                q.append(nx)
                path[nx] = x
    
    
n, k = map(int, input().split())
visited = [0]*100001 # 방문여부 및 해당 거리까지 걸리는 시간
path = [0]*100001 # 해당 거리까지 오기 바로 전 지점 기록 
bfs(n, k, visited, path)