백준 1697번 숨바꼭질 파이썬

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

제출 답안

from collections import deque
import sys
sys.setrecursionlimit(10**7)


def bfs(x):
    cnt = 0
    queue = deque([[x,cnt]])

    while queue:
        x = queue.popleft()
        number = x[0]
        cnt = x[1]
        if not visit[number]:
            visit[number] = True
            if number == m:
                return cnt
            cnt += 1
            if (number - 1) >= 0:
                queue.append([number -1 , cnt])
            if (number + 1) <= 100000:
                queue.append([number + 1, cnt])
            if (number * 2) <= 100000:
                queue.append([number * 2, cnt])
    return cnt

n,m = map(int, input().split())
visit = [False] * 100001
print(bfs(n))

1. 빠르게 담기 위해 deque을 사용한다.
2. x와 cnt를 맨 처음에 담아서 보낸다.
3. 그 다음에 queue가 빌때까지 while문을 돌린다.
4. 우선 숫자와 cnt를 받아서 만약에 숫자에 중복으로 방문하지 않았으면 그 숫자를 방문으로 처리하고 if문을 통해 동시다발적으로 수행한다. number랑 m이 같으면 cnt를 리턴하고 아니면 n-1, n+1n n*2를 동시에 넣어서 수행한다.
5. 이때 cnt도 같이 넘겨서 최종 cnt를 받아온다.

재귀 깊이 설정

import sys
sys.setrecursionlimit(10**7)

• 재귀 깊이가 깊어질때 오류날 수 있어서 깊이를 깊게 설정하였다.