숨바꼭질 4


숨바꼭질 3 문제에 경로 출력이 추가된 문제이다.

BFS를 이용해 최단시간으로 동생을 찾아낸다.

BFS과정은 숨바꼭질 3포스팅을 참고하자.


경로를 추적해보자.

이때, 경로정보를 함께 달고다니면서 BFS를 진행하면 시간초과가 발생한다. (deque를 활용해 좌표들을 추가할 때, 리스트 정보도 함께 넘겨주면 시간초과 발생)

따라서, path 리스트를 별도로 만들어 해당 점으로 이동하기 직전의 좌표를 저장해 놓았다. 예를 들어서 5 - 10 - 9 순서로 이동했을 때, path[9] = 10, path[10]=5 이런식으로 저장했다. 이렇게 저장해 놓으면 마지막 점을 이용해 경로를 복원할 수 있게 된다.


way라는 배열에 마지막 도착지점의 좌표부터 넣어준다. 좌표를 way에 추가하고, 해당 좌표의 path값으로 다시 이동해서 way에 추가하고를 반복한다. 이렇게 저장된 way리스트에는 이동 경로가 마지막 도착지점부터 출발지점까지 거꾸로 저장되어 있음으로 출력할 때는 뒤집어서 출력해준다.

#경로 복원
way=[]
while True:
    way.append(a)
    a=path[a]
    if a == -1:
        print(*way[::-1])
        break


CODE

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

n,k=map(int,read().split())
#해당 좌표까지 이동하는데 걸리는 시간 저장
dp=list(-1 for _ in range(max(n,k)*2+1))
dp[n]=0
#해당 좌표로 오기 이전의 좌표 저장(경로 확인 용도)
path=list(0 for _ in range(max(n,k)*2+1))
path[n]=-1
#BFS
point=deque([n])
while point:
    a=point.popleft()
    #동생을 찾은 경우 시간과 경로를 출력하고 시스템을 종료한다.
    if a==k:
        print(dp[a])
        way=[]
        #경로 복원
        while True:
            way.append(a)
            a=path[a]
            if a == -1:
                print(*way[::-1])
                break
        sys.exit()
    else:
        if a-1>=0 and dp[a-1]==-1:
            dp[a-1]=dp[a]+1
            path[a-1]=a
            point.append(a-1)
        if a+1<=k*2 and dp[a+1]==-1:
            dp[a+1]=dp[a]+1
            path[a+1]=a
            point.append(a+1)
        if a*2<=k*2 and dp[a*2]==-1:
            dp[a*2]=dp[a]+1
            path[a*2]=a
            point.append(a*2)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]