문제 설명

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

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

입력

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

출력

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

풀이 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())

visited = {n: True}
position = deque([{n}])
count = 0
while position:
    cur_set = position.popleft()

    if k in cur_set:
        print(count)
        break
    else:
        next_set = set()
        for cur in cur_set:
            visited[cur] = True
            # 메모리 초과를 막기 위해 0, 100000 범위를 지정했더니 해결됨
            if (cur - 1) not in visited and cur - 1 >= 0:
                next_set.add(cur - 1)
            if (cur + 1) not in visited and cur + 1 <= 100000:
                next_set.add(cur + 1)
            if (cur * 2) not in visited and cur * 2 <= 100000:
                next_set.add(cur * 2)
        position.append(next_set)
        count += 1

백준 : [Silver I] 숨바꼭질

문제 설명

입력

출력

풀이 코드

CHECK!