[실버 1] 백준 1697 - 숨바꼭질 (파이썬)

https://www.acmicpc.net/problem/1697

풀이

수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있다. 수빈이는 1초에 다음 세 가지 행동 중 하나를 선택할 수 있다:

• X - 1로 이동 (1초 소요)
• X + 1로 이동 (1초 소요)
• 2 * X로 순간이동 (1초 소요)

목표는 수빈이가 동생에게 도달하는 데 걸리는 최소 시간을 구하는 것이다.

이 문제는 각 위치를 정점으로 보고, 가능한 이동을 간선으로 간주하여 최단 거리를 구하는 그래프 탐색 문제로 볼 수 있다.

특정 위치에서 세 방향으로 이동 가능하므로, 그래프 탐색을 통해 가장 먼저 도착하는 경우가 최소 시간이 된다.

BFS는 그래프에서 최단 거리를 구할 때 매우 적절한 알고리즘이다. BFS는 먼저 도달한 경로가 최단 경로임을 보장하므로, 동생의 위치에 처음 도달했을 때의 시간이 곧 정답이 된다.

1. 방문 배열(dist[]) : 각 위치(0~100000)에 대해 방문 여부와 해당 위치에 도달하는 데 걸린 시간을 저장한다. 초기값은 -1로 설정하고, 시작 위치는 0으로 초기화한다.
2. 큐(Queue) : 현재 위치에서 이동할 수 있는 세 경우를 모두 큐에 넣어가며 탐색한다.
3. 조건 검사 : 이동하려는 위치가 0 이상 100000 이하의 범위를 벗어나지 않고, 아직 방문하지 않은 곳이어야 한다.

코드

# 백준 1697 - 숨바꼭질
# 분류 : BFS
# 문제집 - 0x09강 - BFS

from collections import deque

N, K = map(int, input().split())
MAX = 1000001

dist = [-1] * MAX
dist[N] = 0

queue = deque([N])

while queue :
    current = queue.popleft()

    if current == K :
        break

    for next in (current - 1, current + 1, current * 2) :
        if 0 <= next < MAX and dist[next] == -1 :
            dist[next] = dist[current] + 1
            queue.append(next)

print(dist[K])