[Python - 백준 1697] 숨바꼭질

1697번: 숨바꼭질

문제 설명

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

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

입력형식

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

출력형식

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

입출력 예시

풀이 과정

간단한 BFS에다 시간을 dist에 저장해주면 되는 간단한 문제였다. BFS 문제 방식에 대해 알면 쉽게 풀 수 있었다. 

1초 후 마다 이동할 수있는 거리인 현재 +1, 현재 -1, 현재 *2 을 for문에 넣어 조건문을 검사하도록 하였고 최대 값이 100,000이므로 100,000*2배인 200,000을 MAX 값으로 설정했다.

 

from collections import deque

def bfs(n, k):
    queue = deque([n])
    visited[n] = True
    while queue:
        now = queue.popleft()
        for move in [now+1, now-1, now*2]:
            if 0<= move <= MAX and not visited[move]:
                visited[move] = True
                queue.append(move)
                dist[move] = dist[now]+1
    return dist[k]





if __name__ == '__main__':
    n, k = map(int,input().split())
    MAX = 200000
    visited = [False]* (MAX+1)
    dist = [0]* (MAX+1)
    print(bfs(n,k))