[백준] #13549 숨바꼭질3(python)

📌문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

백준 13549번 문제

💡Idea

물통 문제와 비슷하게, BFS를 활용하여 풀 수 있는 문제입니다.

수빈이의 위치를 노드, 수빈이가 이동할 수 있는 방법 3가지(X - 1, X + 1, 2 * X)를 세 개의 edge라고 생각하여 동생의 위치와 동일한 노드를 찾아 가는 그래프 탐색의 방법으로 생각하면 쉽습니다.

💻코드

• ⏰ 시간 : 224 ms / 메모리 : 39036 KB

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
queue = deque([(0, N)]) # (시간, 현재 위치)의 형태로 queue
visited = set() # 이미 방문한 위치 노드들의 집합
while queue: # BFS 수행
    sec, pos = queue.popleft() #(해당 위치까지 가는 시간, 현재 위치)
    if pos == K: # 동생 위치에 도달했으면 출력 후 종료
        print(sec)
        break
    if pos not in visited:
        visited.add(pos)
        # 순간이동하는 경우
        if 0 <= pos * 2 <= 100000: queue.appendleft((sec, pos * 2))
        # X + 1로 이동하는 경우
        if 0 <= pos + 1 <= 100000: queue.append((sec + 1, pos + 1))
        # X - 1로 이동하는 경우
        if 0 <= pos - 1 <= 100000: queue.append((sec + 1, pos - 1))

📝코드 설명

주의할 점

📌 첫 번째 주의할 점은, 단순한 BFS 문제처럼 노드의 수가 정해져 있는 것이 아니기 때문에 queue에 노드를 넣을 때 범위를 잘 지정해주어야 한다는 것입니다.

예를 들어, 수빈이는 자신의 위치의 2배씩 이동할 수 있습니다. 이 때 수빈이의 위치를 제한해주지 않으면 수빈이의 위치를 무한히 증가시키며 queue에 넣어주기 때문에 메모리 초과가 납니다.

📌 두 번째 주의할 점은, 순간 이동 하는 경우에 우선순위를 더 높게 줘야 한다는 것입니다.

X + 1로 이동하거나 X - 1로 이동하는 경우는 1초 시간이 걸리지만, 2 * X로 순간이동하는 경우에는 시간이 증가하지 않습니다.

최소 이동 시간을 구해야하는 문제이기 때문에 순간이동하는 것을 걷는 것보다 우선시하여 처리해야하고, 그렇기 때문에 순간이동하는 경우에는 queue에 appendleft를 이용하여 값을 넣어줍니다.