백준(baekjoon) 1753번: 최단 경로(골드 5, 파이썬 PYTHON) - 최단 경로

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

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

13549번: 숨바꼭질 3

 

import sys
from collections import deque

N,K=map(int,sys.stdin.readline().split())
answer=[-1 for _ in range(100001)]
queue=deque()

answer[N]=0
queue.append(N)

while queue:
  point=queue.popleft()
  if(point==K):
    print(answer[K])
    break
  if(point>0 and answer[point-1]==-1):
    answer[point-1]=answer[point]+1
    queue.append(point-1)
  if(0<2*point<=100000 and answer[2*point]==-1):
    answer[2*point]=answer[point]
    queue.append(2*point)
  if(point<100000 and answer[point+1]==-1):
    answer[point+1]=answer[point]+1
    queue.append(point+1)

 

※ 최단 경로

 

 

● 현재 수빈이가 있는 지점이 0보다 크고 이 지점보다 하나 전에 있는 지점에 간 적이 없다면, 현재 수빈이가 있는 지점까지 오는데 걸린 최소 시간에 1초를 더한 값을 현재 지점보다 하나 전에 있는 지점에 도달하는데 걸리는 최소 시간으로 갱신해 준 뒤, 하나 전에 있는 지점을 덱에 append 해준다. 

 

● 현재 수빈이가 있는 지점에 2를 곱한 지점이 0초과 100000 이하이고, 2를 곱한 지점에 간 적이 없다면 현재 수빈이가 있는 지점까지 오는데 걸린 최소 시간에 1초를 더한 값을 현재 지점에 2를 곱한 지점까지 도달하는데 걸리는 최소 시간으로 갱신해 준 뒤, 2를 곱한 지점을 덱에 append 해준다(순간이동이 가장 빨리 이동할 수 있는 방법이므로 덱의 젤 앞에 우선적으로 append 해준다). 

 

● 현재 수빈이가 있는 지점이 100000보다 작고 이 지점보다 하나 뒤에 있는 지점에 간 적이 없다면, 현재 수빈이가 있는 지점까지 오는데 걸린 최소 시간에 1초를 더한 값을 현재 지점보다 하나 뒤에 있는 지점에 도달하는데 걸리는 최소 시간으로 갱신해 준 뒤, 하나 뒤에 있는 지점을 덱에 append 해준다. 

 

● 이 과정을 진행하다가 덱에서 popleft 한 값이 동생이 있는 지점 K와 같다면 이 지점에 도달하는데 걸린 최소시간을 출력해준 뒤 while 문을 빠져나오면 답을 구할 수 있다!