BaekJoon 13913번 : 숨바꼭질 4 (python)

BaekJoon 13913번 : 숨바꼭질 4 (G4 30.831%)

링크텍스트

지금까지 풀어보았던 BFS 숨바꼭질의 역추적을 더한 문제이다.
이전에 풀었던 숨바꼭질 문제는 순간이동의 가중치가 달랐기 때문에 Dijkstra로 풀었지만 이번 문제는 가중치가 1로 같으므로 BFS를 이용해서 풀 수 있다.

• 반복문을 통해 -1, 1, x(자신)의 값을 통해 nx를 정의하고 범위안에 들어가고 아직 방문하지 않은 위치라면 방문 여부 체크를 해주고 q에 nx와 count+1을 넣어준다. 그리고 역추적을 하기 위한 dp[nx]는 nx의 이전의 값은 x라는 것을 의미하기 위해 dp[nx] = x를 넣어준다.
• while문이 다 끝나고 dp를 K에서부터 이전의 인덱스로 계속 이동하며 result배열에 값을 해당 인덱스를 넣어주고 시작점 N에 도달하게 되면 역추적을 마무리한다.

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int,input().split())
q = deque()
q.append((N,0))
dp = [-1]*100001
check = [False]*100001
check[N] = True

while q :
    x, count = q.popleft()
    if x == K :
        print(count)
        break
    for i in [-1,1,x] :
        nx = x + i
        if 0<= nx <=100000 and not check[nx] :
            check[nx] = True
            q.append((nx,count+1))
            dp[nx] = x

result = list()
while K != -1 :
    result.append(K)
    K = dp[K]
print(*result[::-1])