[Python | 백준] 1697번: 숨바꼭질

문제 요약

수빈 현재 위치 N, 동생 현재 위치 K, 0부터 100,000 까지의 정수

수빈이가 동생을 찾을 수 있는 가장 빠른 시간 구하기.

수빈이가 이동할 수 있는 건 3가지 : X-1, X+1, 2*X

 

풀이

시작 노드에 연결된 노드는 3개, 각 노드에서 1초가 지날 때마다 하나씩 이동하다가,

목표 노드에 도착하면 걸린 시간 리턴

-> BFS로 풀이할 수 있다

 

def bfs(n, k):
    if n == k: # 같다면 걸린 시간 0
        return 0

    visited = [False] * 100001 # 입력 값 범위보다 크게
    queue = deque([(n, 0)]) # n에는 현재 노드 위치, 0에는 걸린 시간 저장

    while queue:
        cur, time = queue.popleft()

        # X - 1
        if cur > 0 and not visited[cur - 1]:
            if cur - 1 == k:
                return time + 1
            visited[cur - 1] = True
            queue.append((cur - 1, time + 1))

        # X + 1
        if cur < 100000 and not visited[cur + 1]:
            if cur + 1 == k:
                return time + 1
            visited[cur + 1] = True
            queue.append((cur + 1, time + 1))

        # 2 * X
        if cur * 2 <= 100000 and not visited[cur * 2]:
            if cur * 2 == k:
                return time + 1
            visited[cur * 2] = True
            queue.append((cur * 2, time + 1))

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

print(bfs(n, k))