[백준] 13549번 문제 (숨바꼭질 3) 파이썬(Python) 풀이

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

13549번: 숨바꼭질 3

from collections import deque
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
visited = [False] * 100001
q = deque()
q.append([n, 0])

min_count = sys.maxsize

while q:
    cur, count = q.popleft()
    visited[cur] = True

    if cur == k:
        min_count = min(min_count, count)

    if 0 <= cur + 1 < 100001 and not visited[cur + 1]:
        q.append([cur + 1, count + 1])
    if 0 <= cur - 1 < 100001 and not visited[cur - 1]:
        q.append([cur - 1, count + 1])
    if 0 <= cur * 2 < 100001 and not visited[cur * 2]:
        q.append([cur * 2, count])

print(min_count)

전형적인 bfs 문제다.

bfs를 알고 있다면 어렵지 않게 풀 수 있다.

한 가지 주의할 점은 순간이동은 0초 만에 갈 수 있다고 했으니 count를 queue에 추가할 때 그 값 그대로 추가하는 점이다.