February 16, 2023

13549번: 숨바꼭질 3

문제 요약

• 점 N(0 ≤ N ≤ 100,00)에서 점 K(0 ≤ K ≤ 100,000)까지 아래의 연산을 최소한으로 거쳐 이동하는 경우의 수
  • X - 1
  • X + 1
  • X * 2 (연산 횟수에 포함하지 않는다.)

풀이

from collections import deque
from sys import maxsize

N, K = map(int, input().split())
result = maxsize
visited = [maxsize] * 200_001

def bfs():
    global result

    q = deque()

    q.append((N, 0))

    while (q):
        node, time = q.popleft()

        if (visited[node] < time):
            continue

        if (node == K):
            result = min(result, time)

        visited[node] = time

        if (node < K and node + 1 <= 200_000 and visited[node + 1] > time + 1):
            q.append((node + 1, time + 1))

        if (node - 1 >= 0 and visited[node - 1] > time + 1):
            q.append((node - 1, time + 1))

        if (node < K and node * 2 <= 200_000 and visited[node * 2] > time):
            q.append((node * 2, time))

bfs()

print(result)

• BFS 이용
• 이후에 큐에 삽입되었더라도, 이전에 삽입된 노드보다 더 낮은 시간일 수 있음에 유의