2022.02.19 [백준] (python 파이썬) 숨바꼭질 4

 

 

 

 

 

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

13913번: 숨바꼭질 4

 

---

풀이

이 문제는 최단 거리를 찾는 문제이기 때문에 bfs를 사용했다.

또한 최단 거리로 목표지점으로 가기위한 경로를 출력해야 했기 때문에 route배열을 이용해 해당 인덱스로 가기 위한 이전 인덱스를 저장했다. 1에서 출발해서 10까지로 예를 들면 아래와 같다.

1	2	3	4	5	6	7	8	9	10
0	1		2	4					5

위와 같이 배열에 이전의 위치가 저장되어있다. 값을 모두 구한 뒤, for문을 이용해 역으로 목표지점부터 시작지점까지 다른 배열에 담은 후, reversed를 이용해 역으로 출력했다.

from collections import deque
 
n,k=map(int, input().split())
 
time=[-1]*100001
route=[0]*100001
 
def bfs():
    deq=deque()
    deq.append(n)
    time[n]=0
    while deq:
        x=deq.popleft()
        if x==k:
            break
        for i in [x*2,x+1,x-1]:
            if 0<=i<=100000 and time[i]==-1:
                if i==x*2:
                    deq.append(i)
                    time[i]=time[x]+1
                    route[i]=x
                if i==x+1:
                    deq.append(i)
                    time[i]=time[x]+1
                    route[i]=x
                if i==x-1:
                    deq.append(i)
                    time[i] = time[x] + 1
                    route[i] = x
bfs()
print(time[k])
arr=[]
arr.append(k)
x=route[k]
for _ in range(time[k]):
    arr.append(x)
    x=route[x]
for i in reversed(arr):
    print(i,end=' ')