수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력) 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력) 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
방문한 위치를 또 방문하게 될 경우, 그 다음 방문 위치는 동일하기 때문에 경우의 수가 미친듯이 늘어남
그러면 방문한 곳은 방문했다고 표시하고 방문하지 않아야 함
: 이후 방문할 위치가 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))
: 미리 다음 방문 위치가 visited 인지 체크를 하고 이미 방문했다면 append 안함