[벡준 1697번] 숨바꼭질 - 파이썬(python)

1697번: 숨바꼭질

분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

문제

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

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

입력

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

출력

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

풀이

• 입력받은 수 n에서 k까지 이동하는데 걸린 시간을 구하는 문제이다.
• 이동할 수 있는 방법은 x-1, x+1, x*2 이렇게 3가지의 방법이 있다.
• 따라서 n의 범위인 100001까지 방문배열을 만들고 방문체크해나가며 동생의 위치에 도달했을 때 리턴한다. (방문배열의 k에 있는 수가 정답)

코드

from collections import deque

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

    while q:
        x = q.popleft()
        # 동생의 위치에 도달하면 리턴
        if x == k:
            return visit[x]

        # 현재좌표에서 갈수있는 모든 경우 x-1, x+1, 2*x를체크하고 q에 넣기
        for i in (x-1, x+1, 2*x):
            if 0 <= i <= 100000 and visit[i]==0:
                visit[i] = visit[x] + 1
                q.append(i)


n, k = map(int, input().split())
# n의 범위에 따른 방문 배열
visit = [0] * 100001

print(bfs(n, k))