BOJ 1697. 숨바꼭질 (Python)

문제

BOJ 1697

내가 생각한 풀이

크기가 100_001인 dist 배열을 만들고 -1로 초기화한다.

dist[N]의 값을 0으로 수정한다.

for문으로 순간이동하거나 걷는 거리를 돌며 방문하지 않은 좌표를 방문하고 dist 수정

 

코드 (Python)

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

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

dist = [-1] * 100_001
dist[N] = 0

queue = deque([N])
while queue:
    xp = queue.popleft()
    if xp == K:
        print(dist[K])
        exit(0)
    for res in [xp*2, xp+1, xp-1]:
        if not (0 <= res <= 100_000):
            continue
        if dist[res] == -1:
            queue.append(res)
            dist[res] = dist[xp] + 1