[BOJ] #1697 - 숨바꼭질

1697번: 숨바꼭질

 

 

** 문제 유형

• BFS

 

** 풀이

1. 특정 위치까지 이동하는 최단 시간을 계산하는 문제
2. 이동 시간이 모두 1초로 동일하므로, 간단히 BFS를 이용하여 해결 가능 (간선의 가중치 = 1)
3. 큐 구현을 위해, collections 라이브러리의 deque 클래스 사용

 

from collections import deque

def bfs():
    q = deque([n])

    while q:
        now_pos = q.popleft()

        if now_pos == k:
            return array[now_pos]

        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 # 이전 정점까지 걸린 시간 + 1

                q.append(next_pos) # 이동할 다음 정점 저장

---

MAX = 100001 # n = 0,  k = 100000 일 때

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

array = [0] * MAX # 총 이동 시간 누적

print(bfs())