[백준] 1697번 숨바꼭질

문제

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

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

입력

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

출력

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

풀이

from collections import deque

n,m = map(int, input().split())
# 최대 크기 만큼 생성
MAX = 10**5
# 방문 리스트 생성
visited = [0]*(MAX + 1)
# 최초로 방문한 횟수가 곧 최소 방문 횟수이므로, 가장 먼저 방문할 수 있도록만 고려하기.
def bfs(n):
    q = deque([n])
    while q:
        a = q.popleft()
        # 만약 a가 m에 도달했다면, 멈춤
        if (a == m):
            return visited[a]
        for i in (a-1 , a+1, a*2):
            if (0 <= i <= MAX) and not visited[i]:
                visited[i] = visited[a] + 1
                q.append(i)
print(bfs(n))      
    

후기

• 해당 문제를 풀 때, 풀이를 좀 보고 풀었다. 솔직히 아이디어가 부족했던 부분이라서, 문제를 많이 풀면 해결될 거 같다.
• 추가로, MAX 변수를 선언할 때, 소문자와 대문자를 잘 구분해서 사용해야 겠다. 솔직히 실수가 큰 거 같다.