백준 13913 | 숨바꼭질 4 | python 풀이

문제

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

내 답안

# 13913 숨바꼭질4
from collections import deque

n, k = map(int, input().split())
visited = [[0, -1] for _ in range(100001)]
visited[n][0] = 1
d = deque([n])

while d:
  cur = d.popleft()
  if cur == k:
    print(visited[cur][0] - 1)  # 시간 출력
    break

  for i in range(3):
    if i == 0:
      next = cur + 1
    elif i == 1:
      next = cur - 1
    else:
      next = cur * 2

    if 0 <= next < 100001 and visited[next][0] == 0:
      visited[next][0] = visited[cur][0] + 1
      visited[next][1] = cur
      d.append(next)

# 이동 경로 출력
cur = k
revAns = [k]  # 경로 저장 배열
while True:
  cur = visited[cur][1]
  if cur == -1:
    break
  else:
    revAns.append(cur)

print(*revAns[::-1])

해설

숨바꼭질 문제 시리즈를 풀어봤다면 쉽게 해결 할 수 있는 문제였다.

 

다만 지나온 경로를 저장해야 한다는 점이 다른 문제와의 차이점인데,

이는 visited 배열에 카운트와 직전 위치 정보를 저장하면 쉽게 해결할 수 있다.

 

목적지에 도착하면 카운트만 먼저 출력하고, 직전 위치에서 출발해서 시작점까지 백트래킹 하듯 이동 경로를 되짚어가면 된다.

 

피드백

• 처음 풀이에서는 visited[][1]에 지나온 모든 경로를 저장했는데 메모리 초과 오류가 떴다. 모든 경로를 저장하지 않고 직전 위치만 저장함으로써 오류를 해결할 수 있었다.