[DFS, BFS] 백준 13913번: 숨바꼭질 4 / 골드 4

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

13913번: 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

import collections
n, k = map(int, input().split())
count = 0
visit = [False]*(100000+1)
prev = {}

if n == k:
    print(0)
    print(n)
    quit()


def makeOrder(pos):
    ord = [pos]
    cur = pos
    while cur != n:
        ord.append(prev[cur])
        cur = prev[cur]
    return reversed(ord)


q = collections.deque()
q.append(n)
while q:
    for _ in range(len(q)):
        pos = q.popleft()
        next = [pos - 1, pos + 1, 2 * pos]
        for i in range(3):
            if next[i] == k:  # finish
                prev[next[i]] = pos
                print(count+1)
                print(*makeOrder(next[i]))
                quit()

            if 0 <= next[i] <= 100000 and not visit[next[i]]:
                visit[next[i]] = True
                q.append(next[i])
                prev[next[i]] = pos
    count += 1

기존 숨바꼭질 문제와 비교했을 때 루트까지 출력을 해야되는 문제다.

처음엔 q를 이차원 배열로 설정하고 두번째 인자로 그 전 루트를 모두 담고 있는 리스트를 만들어 넘겨주었는데

이렇게하면 시간초과가 발생하고 만다.

해결법은 이전 위치 정보를 딕셔너리로 만들어서 target 지점에 도착했을 시 루트를 역추적하는 방법이다.