백준 13913번 : 숨바꼭질 4 in Python

13913번: 숨바꼭질 4

 

www.acmicpc.net

이 문제는 기존의 숨바꼭질 문제에서 가장 빠르게 동생을 찾는 시간뿐만 아니라 어떻게 이동해야 하는지 그 경로도 출력해야 한다.

백준 1697번 : 숨바꼭질 in Python

1697번: 숨바꼭질 www.acmicpc.net 위 문제는 어떤 한 점에서 다른 한 점으로 가기 위해 걸리는 최단 시간을 구하는 문제로, 이동 방법에는 앞뒤로 한 칸 또는 그 점의 좌표만큼 앞으로 이동하는 방법이 있다. 만..

wanna-be-developer-yjh.tistory.com

그래서 위 링크의 풀이에서 큰 차이는 없으나 visited 배열을 이동 경로 출력을 보조하기 위한 배열인 prev로 대체한다. prev의 원소들은 -1로 초기화한다. BFS 과정에서 특정 정점 u와 인접한 정점들에 대해 방문할 때 이전에 방문한 적이 있는지는 prev의 해당 정점에 대응하는 값이 -1이 아닌지로 판단한다. 그리고 인접한 정점을 방문할 때 prev 배열에서 그 정점에 대응하는 값을 u로 한다. 

이후 K까지 도달하기 위한 경로를 출력할 때는 prev 배열에서 K번째 인덱스를 시작으로 N에 도달할 때까지 경로를 역으로 추적한다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N, K = map(int, input().split())
bfs = [0 for _ in range(100001)]
# 경로 출력을 보조하기 위한 배열
prev = [-1 for _ in range(100001)]
queue = deque()
queue.append(N)
while len(queue) > 0:
    u = queue.popleft()
    if u == K: break
    # 방문하지 않은 정점의 경우 prev의 원소의 값이 -1이다.
    if u<100000 and prev[u+1] == -1:
        queue.append(u+1)
        bfs[u+1] = bfs[u] + 1
        prev[u+1] = u
    if u>0 and prev[u-1] == -1:
        queue.append(u-1)
        bfs[u-1] = bfs[u] + 1
        prev[u-1] = u
    if u<=50000 and prev[2*u] == -1:
        queue.append(2*u)
        bfs[2*u] = bfs[u] + 1
        prev[2*u] = u
print(bfs[K])
# 경로 추적을 위한 코드
res = str(K)
k = K
while k != N:
    res = str(prev[k]) + ' ' + res
    k = prev[k]
print(res)