[백준/Python] 13549번: 숨바꼭질 3

문제

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

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

입력

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

풀이

N부터 시작하는 위치를 deque에 넣고, visited배열로 각 위치의 방문 여부(-1로 초기화)와 최소 시간을 업데이트 해나간다.

BFS 알고리즘으로 풀 수 있다.

코드

from collections import deque

n, k = map(int, input().split())

def bfs(n, k):
    MAX = 100001
    visited = [-1] * MAX  # -1로 초기화
    
    dq = deque()
    dq.append(n)
    visited[n] = 0

    while dq:
        current = dq.popleft()
        
        if current == k:
            return visited[current]

        # 순간이동은 deque의 앞에 추가, 이동은 뒤에 추가
        if 0 <= current * 2 < MAX and visited[current * 2] == -1:
            visited[current * 2] = visited[current]  # 시간 추가 없음
            dq.appendleft(current * 2)  
        
        if 0 <= current - 1 < MAX and visited[current - 1] == -1:
            visited[current - 1] = visited[current] + 1
            dq.append(current - 1)
        
        if 0 <= current + 1 < MAX and visited[current + 1] == -1:
            visited[current + 1] = visited[current] + 1
            dq.append(current + 1)

print(bfs(n, k))