백준 13913번 파이썬 - 숨바꼭질4

 

13913번: 숨바꼭질 4

문제풀이

숨바꼭질 문제에서 이동경로가 추가된 문제로, 부모의 위치를 배열에 저장하는 방법으로 문제를 풀 수 있다.
예를 들어, 5 - 10 - 9 - 18 - 17 => 이 경로에서 path[10] = 5, path[9] = 10, path[18] = 9, path[17] = 18

이렇게 부모의 위치를 차곡차곡 배열에 할당해주고, 수빈이의 위치인 k에 도달했을 때, 부모의 위치를 index로 이용해서 이동 경로를 알아낼 수 있다.

:( 나는 메모리 초과가 나왔었는데, 자식이 그 전 경로까지 다 저장하는 방식으로 풀었어서 메모리가 부족했던 것이었다. 이렇게 간단히 부모 위치만 배열에 저장해도, 거꾸로 타고 올라가서 그 경로를 알아낼 수 있다.

그래프 그림

이동경로 저장을 그림으로 표현

코드

from collections import deque

n, k = map(int, input().split())
dist = [0] * (10**5 + 1)# 최소 이동 경로 시간
path = [0] * (10**5 + 1)# 이동 경로를 저장하는 배열, 각 부모 및 부모위치를 저장.
def show_path(x):# k에 도달했을 때, 끝에서 부터 값을 꺼내는 방식.
    arr = []
    temp = x
    for _ in range(dist[x] + 1):
        arr.append(temp)
        temp = path[temp]
    for i in arr[::-1]:# 거꾸로 저장되어 있으니, arr[::-1]로 처음경로 부터 출력
        print(i, end=' ')

def bfs():
    q = deque([n])
    while q:
        v  = q.popleft()
        if v == k:
            print(dist[k])
            show_path(k)
            break
        for nx in (v - 1, v + 1, v * 2):
            if nx >= 0 and nx <= 10 ** 5 and not dist[nx]:
                q.append(nx)
                path[nx] = v
                dist[nx] = dist[v] + 1

bfs()

 

참고

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