[백준] 13549. 숨바꼭질 3(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 13549. 숨바꼭질 3

시간 제한	메모리 제한	난이도
2초	512 MB	골드 5

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

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

✔️ 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

✔️ 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

✔️ 입력 출력 예시

입력	출력
5 17	2

🗒️ 내 풀이

[1697. 숨바꼭질]에서 2*X의 위치로 이동 시간이 0초로만 바뀐 문제로, 역시 BFS로 해결할 수 있다.

이 문제에서는 시간이 0인 이동과 1인 이동을 따로 처리해주면 쉽게 해결이 가능하다.

근데 나는 여기서 범위를 잘못 적어서 (while문에서 범위 판단 시 100001을 10001로 썼음) 괜한 시간낭비를 했다. 따라서 앞으로는 범위나 문제 마다 있는 특정 값을 계속 써야할 때는, 꼭 변수로 등록하고 쓰자! 그리고 값도 웬만하면 복사해서..

import sys
from collections import deque
input = sys.stdin.readline
MAX = 100001
n, k = map(int, input().split())
dist = [-1] * MAX 
q = deque([n])
dist[n] = 0
while q:
    x = q.popleft()
    if x == k:
        print(dist[k])
        break
    if 2 * x < MAX and dist[2 * x] == -1:
        q.append(2 * x)
        dist[2 * x] = dist[x]
    for i in [x - 1, x + 1]:
        if 0 <= i < MAX and dist[i] == -1:
            q.append(i)
            dist[i] = dist[x] + 1

💡 TIL

앞으로는 범위나 문제 마다 있는 특정 값을 계속 써야할 때는, 값은 웬만하면 복사하고 꼭 변수로 등록하고 쓰자!!