[백준] 13913번 : 숨바꼭질 4 (파이썬/Python) - BFS 풀이

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

13913번: 숨바꼭질 4

숨바꼭질 1 번문제와 문제는 같은데, 업그레이드 된 부분은 수빈이가 동생을 찾을 수 있는 가장 빠른 시간에 대한 경로를 저장해두어야 한다는 것이다. 
경로 저장을 위해 note라는 배열을 생성한다. 

for nx in [now-1, now+1, now*2]:
    if 0 <= nx <= MAX and not visited[nx]:
        visited[nx] = visited[now] + 1
        queue.append(nx)
        note[nx] = now # 다음 이동 위치에 현재 위치 기록하기

그리고 새로 이동할 위치에 해당하는 nx좌표로 이동하기 이전에 now 라는 위치에 있었다는 의미로 note[nx] = now 저장을 해둔다. 

if now == k:
    print(visited[now])
    get_path(now)
    break

현재 위치가 k 에 도달했을 때 get_path 함수를 호출하여, k까지 최단거리로 이동해온 경로를 출력한다. 

def get_path(now):
    path = []
    temp = now
    for i in range(visited[now]+1): # 목표지점까지 탐색하는데 걸린 거리만큼 저장된 경로를 하나씩 note 리스트에서 꺼낸다.
        path.append(temp)
        temp = note[temp]

    print(*path[::-1])

 

 

from collections import deque 

n, k = map(int, input().split())
MAX = 100000
visited = [0] * (MAX + 1)
note = [0] * (MAX+1) # 경로 저장을 위한 배열

def bfs():
    queue = deque() # 현재 위치, 시간, 이동경로
    queue.append(n)
    while queue:
        now = queue.popleft()
        if now == k:
            print(visited[now])
            get_path(now)
            break

        for nx in [now-1, now+1, now*2]:
            if 0 <= nx <= MAX and not visited[nx]:
                visited[nx] = visited[now] + 1
                queue.append(nx)
                note[nx] = now # 다음 이동 위치에 현재 위치 기록하기

def get_path(now):
    path = []
    temp = now
    for i in range(visited[now]+1): # 목표지점까지 탐색하는데 걸린 거리만큼 저장된 경로를 하나씩 note 리스트에서 꺼낸다. 
        path.append(temp)
        temp = note[temp]

    print(*path[::-1])

bfs()