[백준1697번] 숨바꼭질 / Python3

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

4

나의 풀이

0 ~ 100000 만큼의 배열을 만들고 걸어서 가는 (+1, -1)과 순간이동을 하는 (*2)의 경우들을 BFS로 탐색을 하면서 시간을 1씩 증가 시키면서 k와 같아지는 순간 시간을 출력하면 되는 문제이다.

주의할 점은 방문한 곳을 또 방문하면 안된다는 것이다. 만약 그렇게 된다면 큐에 너무 많이 들어가서 메모리초과가 발생하게 된다. 따라서 이미 배열의 값이 0이 아니라면 방문을 했다는 의미이므로 큐에 넣지 않으면 된다.

코드

# 1697번 숨바꼭질
from collections import deque

# bfs
def find(street,n,k):
    q = deque()
    q.append(n)

    dp = [-1,1]
    while q:
        pos = q.popleft()

        # 걷기
        for i in range(2):
            np = pos + dp[i]

            if 0 <= np <= 100000 and street[np] == 0:
                if np == k:
                    return street[pos] + 1
                else:
                    street[np] = street[pos] + 1
                    q.append(np)

        # 순간이동
        np = pos * 2

        if np <= 100000 and street[np] == 0:
            if np == k:
                return street[pos] + 1
            else:
                street[np] = street[pos] + 1
                q.append(np)

# main
n, k = map(int, input().split())
street = [0] * 100001

if n == k:
    print(0)
else:
    print(find(street,n,k))