[백준13549번] 숨바꼭질 3 / Python3

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

2

나의 풀이

N과 시간을 가지고 각 +1, -1, *2의 경우를 BFS를 돌려주면 되는 문제였다. 불필요한 중복 방문을 피하기위해 방문 여부를 담는 visited라는 리스트를 만들어두고 큐에서 pop이 될때마다 방문 표시를 해주었다. 또 각 N과 K의 범위인 0부터 100,000의 범위 안인지를 확인해주고 각 계산에 따라 +1, -1, *2를 한 값을 큐에 넣어주었다. *2를 해주는 경우에만 cnt를 증가시키지 말아야한다. 그리고 주의해야할 점은 다른 대부분의 BFS문제들은 조건이 맞으면 바로 출력을 하거나 return을 해주었지만 여기서는 최솟값을 저장하는 변수를 두고 BFS가 모두 끝날때까지 최솟값을 찾아야했다. 왜냐하면 2배로 증가하는 경우 cnt가 증가하지는 않지만 큐의 뒷부분에 push가 되어 cnt가 더 큰 상황에서 k와 같은 값이 나올 수 있기때문이다.

코드

# 13549번 숨바꼭질 3
from collections import deque

# main
n, k = map(int, input().split())

answer = float('inf')

q = deque()
q.append([n,0])

visited = [False for _ in range(100001)]
visited[n] = True

while q:
    soo, cnt = q.popleft()
    visited[soo] = True

    if soo == k:
        answer = min(answer, cnt)

    if soo*2 < 100001 and not visited[soo*2]:
        q.append([soo*2,cnt])

    if soo+1 < 100001 and not visited[soo+1]:
        q.append([soo+1,cnt+1])

    if 0 <= soo-1 and not visited[soo-1]:
        q.append([soo-1,cnt+1])

print(answer)