[solved.ac 실버1] 1697_숨바꼭질 (BFS 풀이)

제한 사항

문제

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

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

입력

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

출력

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

예제

예제

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

---

나의 풀이

# BFS
from collections import deque

n, k = map(int, input().split())
queue = deque([n])
d = [0] * 100001

while queue:
    num = queue.popleft()
    if num == k:
        print(d[k])
        break
    for nx in (num-1, num+1, num*2):
        if nx in range(0, 100001) and not d[nx]:
            d[nx] = d[num]+1
            queue.append(nx)

BFS로 풀이했다.

queue에 n을 넣고 시작했다.

queue에서 꺼낸 값이 k라면 d[k] 값을 출력하고 반복문을 빠져나온다.

k가 아니라면 꺼낸 값에서 -1, +1, *2 를 한 값을 차례로 확인하는데 그 값이 0과 100,000 사이의 값이면서 d에 저장된 값이 0이라면 d[꺼낸 값] + 1을 저장한다.

그리고 큐에 nx를 저장한다.

채점 결과