[백준]13913 숨바꼭질4 파이썬 python

문제링크

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

13913번: 숨바꼭질 4

https://rrojin.tistory.com/16   -> 1697번에서 추적 경로 탐색가 추가된 문제

[백준]1697번 숨바꼭질 파이썬 python

코드

import sys
from collections import deque
#sys.setrecursionlimit(10**6)#재귀 최대 깊이 설정
 
input = sys.stdin.readline
MAX = 100001
n, k = map(int,input().split())
dq = deque()
dist = [-1]*MAX
route = [-1]*MAX
 
def track(o,d):
    routes = []
    dest = k
    routes.append(k)
    while dest != o:
        routes.append(route[dest])
        dest = route[dest]
    routes.reverse()
    print(' '.join(map(str, routes)))
'''
#역추적 방법2) 재귀
def track(o,d):
    if o!=d:
        track(o,route[d])
        print(d,end=' ')
    else:
        print(o,end=' ')
'''
dist[n]=0#초기 위치(수빈's)
route[n]=n
dq.append(n)
while dq:
    x = dq.popleft()
    if x == k: #도착
        print(dist[k])
        track(n,k)
        break
    for nx in [x+1,x-1,2*x]: #가능한 3가지 행동
        if 0<=nx<MAX and dist[nx]==-1:
            dist[nx]=dist[x]+1
            route[nx] = x #이전 정점이 무엇이었는지 기록
            dq.append(nx)
 
 
 
 
 
 

 

핵심Point

- 가중치가 1인 최단경로 구하는 문제이기에 BFS알고리즘 적용한다.

- 경로를 구하기 위해서 이전에 방문한 정점을 저장한다. (코드에서, route리스트에 해당)

- if 0<=nx<MAX and dist[nx]==-1: 

  두 조건식의 순서가 바뀌면 런타임 에러 (IndexError) 가 발생하니 먼저 범위를 확인해야한다.