[Python] 13913 숨바꼭질 4

[Gold IV] 숨바꼭질 4 - 13913 

[문제 링크](https://www.acmicpc.net/problem/13913)

---

💻 문제 정의

• 1697번. 숨바꼭질
• 12851번. 숨바꼭질 2
• 13549번. 숨바꼭질 3

다음의 문제들과 비슷한 유형의 문제이다. 매 이동마다 X-1, X+1, 2*X의 위치로 이동하게 되는데, 이때 동생을 찾는 가장 빠른 시간과 더불어 어떻게 이동하는지 경로까지 출력해야 하는 문제이다.

💡 접근 및 설계

기존의 숨바꼭질 문제와 접근은 같다. 추가된 점이라면 지나온 경로를 역추적하여 경로를 출력해야 하는 부분이 추가되었다.

✏️ 알고리즘 풀이

def bfs(n, k):
    Q = deque()
    Q.append(n)
    visited[n] = 0

    while Q:
        curr = Q.popleft()

        if curr == k:
            return

        for next in [curr-1, curr+1, 2*curr]:
            if 0 <= next <= 100000 and visited[next] == -1:
                Q.append(next)
                visited[next] = visited[curr] + 1
                route[next] = curr

N, K = map(int, input().split())
visited = [-1] * (100_001)
route = [0 for _ in range(100001)]

bfs(N, K)

BFS를 통해 최단 경로 및 최단 시간을 찾을 수 있다. 해당 점에 방문한 시각은 visited에 저장될 것이다.

result = []
node = K
while node != N:
    result.append(node)
    node = route[node]
result.append(N)

print(*result[::-1])

역추적 부분 코드이다. 먼저 마지막 도달 부분인 K부터 시작하여 route에 저장된 경로를 따라 이동한다. route는 BFS 당시에 기록해두었다.

🗒️ 최종 제출 코드

# 13913 숨바꼭질 4

from collections import deque

def bfs(n, k):
    Q = deque()
    Q.append(n)
    visited[n] = 0

    while Q:
        curr = Q.popleft()

        if curr == k:
            return

        for next in [curr-1, curr+1, 2*curr]:
            if 0 <= next <= 100000 and visited[next] == -1:
                Q.append(next)
                visited[next] = visited[curr] + 1
                route[next] = curr

N, K = map(int, input().split())
visited = [-1] * (100_001)
route = [0 for _ in range(100001)]

bfs(N, K)

result = []
node = K
while node != N:
    result.append(node)
    node = route[node]
result.append(N)

print(visited[K])
print(*result[::-1])

---

💭 오늘의 회고

-