[백준 문제풀이] 13913번 : 숨바꼭질4

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

13913번: 숨바꼭질 4

 

💡 숨바꼭질과 구하는 것은 같지만 해당 경로를 찾는 문제이기 때문에 결과를 먼저 얻고 어떤 경로로 왔는지 되돌아가는 문제였다.

 

하나의 배열을 더 만들어 주고 거기에 몇 번을 지나왔는지를 넣고, path에서 최종 위치를 통해 반대로 탐색하여 출력한다.

 

생각보다 어려웠던 문제! 반대로 도는게 생각보다 어려웠음

 

✔소스코드

import sys
from collections import deque

N,K=map(int,sys.stdin.readline().split())
visited=[0]*100001
next=[0]*100001

def bfs():
    q=deque()
    q.append(N)
    while q:
        a=q.popleft()
        if a==K:
            print(visited[a])
            path(a)
            break
        for i in (a-1,a+1,a*2):
            if 0<=i<100001 and not visited[i]:
                visited[i]=visited[a]+1
                q.append(i)
                next[i]=a
                print(next[i])
    
def path(a):
    result=[]
    temp=a
    for i in range(visited[a]+1):
        result.append(temp)
        temp=next[temp]
    result.reverse()
    print(' '.join(map(str,result)))

bfs()