백준 13913번: 숨바꼭질 4 (Python)

접근

이전에 풀었던 숨바꼭질 문제에서 경로를 구해주는 것이 추가된 문제이다.

숨바꼭질 문제: 2021.04.12 - [코딩/백준 (Python)] - 백준 1697번: 숨바꼭질 (Python)

백준 1697번: 숨바꼭질 (Python)

기존 숨바꼭질 문제에서 BFS 알고리즘을 이용하여 최단거리를 구하였다. 이 알고리즘은 너비 우선 탐색 방법으로써 처음 위치에서 움직일 수 있는 모든 경우를 한번씩 방문한 후, 다음 위치에서 또 이동할 수 있는 경우를 모두 방문하는 식으로 순서대로 탐색하게 된다. 그럼으로써 깊이 방향으로 한단계씩 내려갈 때마다 그 깊이 값을 저장해주게 되면 원하는 목적지에 도착했을 때의 깊이가 최단 이동거리가 된다.

기존 숨바꼭질 문제에서 더 나아가 경로를 계산해주기 위해 dp에 기존에 저장했던 깊이에 더하여 그곳으로 이동해온 바로 직전의 위치를 저장해주었다. 이를 통하여 마지막 목적지에 도착했을 때, 직전 위치를 계속 따라가면 시작점까지의 경로를 역추적할 수 있는 방식이다.

코드를 보는 것이 더욱 이해가 빠를 것이다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())
dp = [[-1, -1] for _ in range(100001)]
# dp의 첫번째 요소는 깊이, 즉 해당 위치까지의 최단거리
# dp의 두번째 요소는 해당 위치로 이동하기 전 바로 직전 위치
dp[n][0] = 0
q = [n]
while dp[k][0] == -1:  # k 위치에서의 최단거리가 정해질 때까지 반복
    now = q.pop(0)
    if 0 <= now - 1 <= 100000 and dp[now - 1][0] == -1:
        q.append(now - 1)
        dp[now - 1] = [dp[now][0] + 1, now]
    if 0 <= now + 1 <= 100000 and dp[now + 1][0] == -1:
        q.append(now + 1)
        dp[now + 1] = [dp[now][0] + 1, now]
    if 0 <= now * 2 <= 100000 and dp[now * 2][0] == -1:
        q.append(now * 2)
        dp[now * 2] = [dp[now][0] + 1, now]
now = k
order = [k]  # 목적지를 경로에 추가
while now != n:  # 시작점을 찾을 때까지 반복
    order.append(dp[now][1])  # 바로 직전 위치를 경로에 저장
    now = dp[now][1]
print(dp[k][0])
print(*order[::-1])  # 저장된 경로를 뒤집어서 출력

더 생각해 볼 것?

매번 이런 코드를 짤 때, 처음 위치와 마지막 위치가 같은 경우를 놓쳐서 한번씩 틀리는 것 같다. 틀리고 나서 금방 찾아서 다행이지만, 미리 놓치지 않도록 구상하는 연습도 필요할 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!