[伯俊13549 Python]鬼ごっこ3(Gold 5,Daextraor BFS)

SOLVE 1

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')

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

# 인접 노드들을 iterable한 값으로 리턴하기 위한 제너레이터 함수
# 코드가 간단해짐
def move(x):
    yield (x-1, 1)
    yield (x+1, 1)
    yield (2*x, 0)

# 다익스트라 알고리즘
def N_to_K(N, K):
    SSSP = [INF]*(100001)
    SSSP[N] = 0
    q = [(0, N)]
    
    while q:
        cnt_time, cnt_x = heapq.heappop(q)
        
        if cnt_time > SSSP[cnt_x]:
            continue
        
        # 0부터 100000까지의 모든 노드들은, 조건 범위 안에서
        # 자신의 -1, +1, *2의 인접 노드를 가짐
        # 그래서 제너레이터를 통해 직접 인접 노드를 구하여 순회하면 됨
        for adc_x, adc_time in move(cnt_x):
            cal_time = cnt_time + adc_time
            
            # 인접 노드로 구한 값이 조건 범위 안에 있어야 함
            if 0 <= adc_x <= 100000 and cal_time < SSSP[adc_x]:
                SSSP[adc_x] = cal_time
                heapq.heappush(q, (cal_time, adc_x))
    
    return SSSP[K]

print(N_to_K(N, K))

SOLVE 2

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

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

# BFS는 한 번 방문한 노드는 다시 방문하지 않음
# 따라서 같은 level에 대하여 인접 노드로의
# 가중치가 0인 2*x부터 방문해야 함
def move(x):
    yield (2*x, 0)
    yield (x-1, 1)
    yield (x+1, 1)

def BFS(start):
    elapsed = [-1]*(100001)
    elapsed[start] = 0
    q = deque([start])
    
    while q:
        cnt_x = q.popleft()
        
        if cnt_x == K:
            return elapsed[K]
        
        for nx, adc_time in move(cnt_x):
            cal_time = elapsed[cnt_x] + adc_time
            if 0 <= nx <= 100000 and elapsed[nx] == -1:
                elapsed[nx] = cal_time
                q.append(nx)

print(BFS(N))