[BOJ] 백준 13549 숨바꼭질 3 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다.

좌우로 이동하는 두 가지의 선택은 동시에 1초 씩 증가하지만 이 문제는 다른 숨바꼭질 문제와 다르게 

*2로 이동하는 선택은 시간이 증가하지 않는다는 특징이 있다.

너비 우선 탐색을 선택했다.

 

 

 

구현 언어: Python

 

from collections import deque


def solve():
    global n, k, sec
    queue = deque()
    # 시작점 세팅
    queue.append(n)
    sec[n] = 0
    
    while queue:
        now = queue.popleft()
        
        # 순간이동: 시간 증가 안함
        if 0 <= 2*now <= 100000:
            if sec[2*now] == -1:
                sec[2*now] = sec[now]
                queue.append(2*now)
        # 좌우이동: 1초 증가
        for next in (now-1, now+1):
            if 0 <= next <= 100000:
                if sec[next] == -1:
                    sec[next] = sec[now] + 1
                    queue.append(next)


n, k = map(int, input().split())
sec = [-1]*100001    # 이동 시간 기록
solve()
print(sec[k])