[백준] 13913번 숨바꼭질 4 파이썬 코드

코드

from collections import deque

subin, dongsang = map(int, input().split())
path = [0]*100001 # 이전에 방문했던 노드를 기록할 리스트
visited = [0]*100001 # 몇 번째로 해당 노드를 방문했는지 기록할 리스트

def bfs(start): # 가중치가 없고, 최단거리를 찾아야하므로 bfs 이용
  queue = deque([start])
  visited[start] = 1 # 출발 전 방문기록
  while queue:
    popnum = queue.popleft()
    if popnum == dongsang: return visited[popnum]-1 # 만약 pop한 값이 동생이 있는 곳과 같다면 함수 종료
    for i in [popnum - 1, popnum +1,popnum*2]: # -1, +1, *2한 값을 리스트에 넣고 찾아준다
      if 0<=i<100001 and visited[i] == 0: # i의 범위와 처음 방문하는 곳인지 확인
        visited[i] = visited[popnum] + 1 # 몇 번째 방문인지 기록
        path[i] = popnum # i번째 인덱스에 이전 방문한 곳을 기록해둔다.
        queue.append(i)
        
print(bfs(subin)) # 몇 번째인지 출력      

route = [dongsang] # 경로를 추적할 리스트 생성
chasing = dongsang # 도착지점을 chasing 변수에 둔다.

while chasing != subin: # chasing 변수가 출발점이 되면 반복문 종료
  chasing = path[chasing] # chasing은 path[chasing] 값을 할당 받는다. => 이전 방문한 노드 반환
  route.append(chasing) # 반환받은 값을 route리스트에 추가
  
print(*route[::-1]) # 역추적한 값이므로, reverse한 값을 출력해준다.

경로 추적하는 아이디어를 복습할 수 있었다.