백준 1697 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS

  • 설명

    • 특정 위치까지 이동하는 최단 시간을 계산
    • 이동 시간이 모두 1초로 동일, BFS를 이용하여 해결

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    from collections import deque

    MAX = 100001
    n, k = map(int, input().split())
    array = [0] * MAX

    def bfs():
        q = deque([n])
        while q:
            now_pos = q.popleft()
            if now_pos == k:
                return array[now_post]
            for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
                if 0 <= next_pos < MAX and not array[next_pos]:
                    array[next_pos] = array[now_pos] + 1
                    q.append(next_pos)

    print(bfs())