Python/BFS BOJ-13913 숨바꼭질 4

Posted on | In

[Python/BFS] BOJ-13913 숨바꼭질 4

📌문제링크

수빈이가 동생을 찾는 시간과 경로를 구하면된다.
두개의 리스트로 문제를 풀 수 있다. visited = 소요시간, past = 부모노드

BFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque
import sys
input = sys.stdin.readline

if __name__ == '__main__' :
    N,K =map(int,input().split()) # 수빈이 위치/ 동생위치
    visited= [0]*1000001
    past= [0]*1000001
    queue = deque([N])
    while queue:
        n = queue.popleft()
        if n==K:
            print(visited[K])
            ans = []
            while n!=N: #past 배열에는 이전에 어떤 노드들을 지나왔는지 기록되어있으니 그 경로를 탐색한다.
                ans.append(n)
                n =past[n]
            ans.append(N)
            ans.reverse() # 거꾸로 출력
            print(' '.join(map(str,ans)))
            break
        for nx in (n+1,n-1,2*n):
            if 0 <= nx < 1000001 and visited[nx] == 0:
                visited[nx] = visited[n]+1 # 시간증가
                queue.append(nx)
                past[nx] = n # 최종 경로 출력시 nx값을 통해 이전위치 알아내기 위해 저장