1. 문제


수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

입력) 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력) 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

2. 풀이 사고 과정


  1. 방문한 위치를 또 방문하게 될 경우, 그 다음 방문 위치는 동일하기 때문에 경우의 수가 미친듯이 늘어남

  2. 그러면 방문한 곳은 방문했다고 표시하고 방문하지 않아야 함

  1. 데크를 사용해서 수행시간을 줄이고 편하게 앞에서부터 순차적으로 pop하자 (popleft)

3. 파이썬 소스코드


  1. visited 체크를 앞부분에 하는 코드

: 이후 방문할 위치가 visited 일 때에도 현재 위치는 visited가 아니므로 조건에 걸리지 않아서 append를 함

그리고 다음 루프에서 visited!=True 조건에 걸림

from collections import deque
def bfs(N):
    count = 0
    q = deque([[N, count]])

    while q:
        v = q.popleft()
        position = v[0]
        count = v[1]
        if visited[position] != True:
            visited[position] = True
            if position == K:
                return count

            count += 1
            if position * 2 <= 100000:
                q.append([position * 2, count])
            if position + 1 <= 100000:
                q.append([position + 1, count])
            if position - 1 >= 0:
                q.append([position - 1, count])
    return count
    

N, K = map(int, input("").split(" "))
visited = [False for _ in range(100001)]
print(bfs(N))
  1. visited 체크를 뒤에 하는 코드

: 미리 다음 방문 위치가 visited 인지 체크를 하고 이미 방문했다면 append 안함