[BOJ]1697号:鬼ごっこ

1.質問

2.アルゴリズム

3.ソースコード

# BFS 탐색을 위한 queue 자료구조
from collections import deque

n, k = map(int, input().split())
MAX = 100000
time = [0] * (MAX + 1) # 수빈이 0에서 100000까지의 각 거리까지의 이동 시간 기록

def bfs(start):
    q = deque()
    q.append(start)
    
    while q:
        x = q.popleft()
        if x == k:
            return
        
        for nx in (x - 1, x + 1, x * 2):
            # 범위 내이고, 아직 이동시간이 기록되지 않았을 경우
            if 0 <= nx <= MAX and time[nx] == 0:
                q.append(nx)
                time[nx] = time[x] + 1
                
bfs(n)
print(time[k]) # k 위치에 기록된 이동시간 출력

4.失敗コード

from collections import deque

n, k = map(int, input().split())
MAX = 100000

def bfs(start, time):
    q = deque()
    q.append((start, time))

    while q:
        x, t = q.popleft()
        if x == k:
            return t
        
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx <= MAX:
                q.append((nx, t + 1))

print(bfs(n, 0))