13913. 숨바꼭질 4 (Python)

 

13913번: 숨바꼭질 4

 

풀이

 BFS를 통해서 탐색을 하는데 전체적으로는 숨바꼭질 2(풀이 링크)와 비슷하다. 차이점은 숨바꼭질 2는 경우의 수를 카운트하는데 숨바꼭질 4는 하나의 케이스에 대해서 경로를 출력해야 한다.

 

 처음에는 최소힙에 리스트 형태로 경로를 담아두고 최소 시간으로 동생의 위치에 도착했을 때 최소힙에 담겨 있던 경로 정보를 꺼내서 그대로 출력하게 했다. 이럴 경우 시간초과가 발생하는데 이는 수빈이와 동생의 위치가 멀리 떨어져 있을 때 경로를 리스트의 형태로 저장하면 저장할 정보가 많아지게 되기 때문이다. 그렇기 때문에 힙에 리스트를 넣어주지 않고 하나의 리스트를 만들어서 그 안에 경로 정보를 넣어주도록 수정했다.

 

 paths[X] 리스트의 정보는 X의 위치에 수빈이가 최소 시간으로 도착했을 때, X로 오기 전에 있었던 위치 정보를 의미한다. 예를 들어 paths[10] = 5라면 이는 10 위치에 최소 시간으로 도착했을 때 이는 5의 위치에서 이동해 왔음을 의미한다. 이렇게 이전 위치 정보들을 기록해두고 K에서 역으로 N까지 추적해 나가면 수빈이의 이동 경로를 구할 수 있다.

 

코드

import heapq
LIMIT = 100_000
INF = float('inf')


# 경로 출력 함수 
# K에서 N까지 역으로 추적 
def printPath():
    now = K # K부터 시작 
    res = []

    while True:
        res.append(now)
        now = paths[now] # 이전 위치 정보를 paths에서 가져온다.

        if now == -1: # -1에 도착하면 탐색 종료 
            break

    res.reverse() # 역으로 추적했기 때문에 리스트를 뒤집어 준다.
    print(*res)


if __name__ == '__main__':
    N, K = map(int, input().split())
    q = []
    heapq.heappush(q, (0, N))  # (시간, 수빈이의 현재 위치)
    visited = [INF for _ in range(LIMIT + 1)] # 방문 처리, visited[X]: X 위치에 도착하는데 걸린 최단 시간 정보
    visited[N] = 0 # 처음 시작 위치의 시간은 0으로 초기화 
    paths = [0 for _ in range(LIMIT + 1)] # 경로 추적 리스트, paths[X]: X 위치에 최단 시간으로 도착했을 때 X 전에 있었던 위치 
    paths[N] = -1 # 처음 시작 위치의 이전 위치는 -1로 초기화 

    while q:
        time, now = heapq.heappop(q)

        if now == K: # 수빈이가 동생의 위치 K에 도착했으면 탐색 종료 
            print(time)
            printPath()
            break

        for X in [now - 1, now + 1, now * 2]:
            if 0 <= X <= LIMIT and time + 1 <= visited[X]:
                heapq.heappush(q, (time + 1, X))
                visited[X] = time + 1
                paths[X] = now