[Python/Silver1/1697] 숨바꼭질

|    문제

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

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

 

|    입력

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

 

|    출력

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

 

 

---

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

class Solution:
    def hide_find(self):
        n,k = map(int, input().split())
        def bfs():
            Q = deque()
            Q.append((n,0))
            visited = [False] * 100_001
            visited[n] = True
            while Q:
                x, cnt = Q.popleft()
                if x == k:
                    print(cnt)
                    return
                a, b, c = x-1, x+1, 2*x
                for dx in (a,b,c):
                    if 0 <= dx <= 100_000 and not visited[dx]:
                        Q.append((dx, cnt+1))
                        visited[dx] = True
        bfs()

if __name__ == "__main__":
    s = Solution()
    s.hide_find()

 

 

|    비고

visited를 set으로 선언하면 메모리 초과가 난다. 주어진 n의 범위가 0부터 100_000이므로 이 크기의 배열을 사용해서 풀어야 한다.