[백준] 1697번: 숨바꼭질

1697번

문제

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다.

만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

어떻게 풀면 좋을까?

5 17

                 5
           (4)  (6)  (10)
   (3  5  8)  (5  7  12)  (9  11  20)
                  ...

위는 백준의 입력 예제인 경우이다. 수빈이는 5, 동생은 K다. 5를 queue에 넣고, n-1, n+1, n*2 인 경우를 모두 체크한다.
물론 수빈이의 위치 n 이 k와 같아지면 그대로 끝내면 되겠다.

그리고 조건의 결과가 0 이상, 입력 제한 조건인 10만 이하, 4, 6, 10 도 queue에 들어갈 것이다.
그리고 시간초를 저장해 나간다. 최초의 위치가 같으면 0초, 그 다음부터는 queue에서 꺼낸 위치까지의 시간초 + 1초가 다음에
수빈이가 갈 곳의 시간으로 저장된다. 쉽게 그냥 0초 다음 행동으로 4, 6, 10 각각의 칸으로 이동할 때 각각 1초 추가되는 것이다.

풀이

    dist = [0] * (MAX + 1)
    n, k = map(int, input().split())
    q = deque()
    q.append(n)

    while q:
        val = q.popleft()
        if val == k:
            print(dist[val])
            break
        for i in (val - 1, val + 1, val*2):
            if 0 <= i <= MAX and not dist[i]:
                q.append(i)
                dist[i] = dist[val] + 1