백준 13549번 숨바꼭질 3 파이썬

박슬빈·2021년 11월 22일
0

알고리즘

목록 보기
30/40

문제

입력 , 출력

solution

import sys
from collections import deque

input = sys.stdin.readline

Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
while dq:
    a = dq.popleft()
    if a == m:
        break
    if a * 2 < Max and dis[a * 2] == -1:
        dq.appendleft(a * 2)
        dis[a * 2] = dis[a]
    if a + 1 < Max and dis[a + 1] == -1:
        dq.append(a + 1)
        dis[a + 1] = dis[a] + 1
    if a - 1 >= 0 and dis[a - 1] == -1:
        dq.append(a - 1)
        dis[a - 1] = dis[a] + 1
print(dis[m])

설명

키포인트

  1. 현재 위치에서 *2 로 이동하는것은 비용이 0 이다.
  2. 1번에 의해서 큐에 제일 앞에 넣어줘서 *2로 이동할 수 있는 모든경우의 수 를 dis(거리)에 저장을 해준다.
  3. 그 이후에 + 1 , -1 거리를 이동하는 경우를 넣어준다.

제일 중요한건 *2로 이동하는 가중치가 0 이기 때문에 체크를 할 경우에
큐에 가장 앞에 넣어주는게 제일 중요한 키포인트

profile
이것저것합니다

0개의 댓글