b_뱀과 사다리게임_16928

문제

1-6까지 건너기가능
중간 뱀(강제로 밑으로 가는 루트)와 사다리(강제로 위로가는 루트)가 존재
이때 100까지 최소한으로 도착하는 횟수는?

답

bfs임을 생각하면 쉽다
bfs하고 새로 갱신되는것만 계속 추가를 해준다.

import sys
import math
from collections import deque

N,M = map(int,sys.stdin.readline().strip().split())

shortroute = {}
for _ in range(N+M):
    a,b = map(int,sys.stdin.readline().strip().split())
    shortroute[a-1] = b-1

arr = [math.inf] * 100
arr[0] = 0

que = deque([0])
def moveshortroute(index,que,arr,value):
    now_index = index
    while now_index in shortroute:
        next = shortroute[index]
        now_index = next
    if index != now_index:
        if arr[now_index] > value: 
            que.append(now_index)
            arr[now_index] = value
            # print(index,now_index,value)
        return True
    return False

while que:
    i = que.popleft()
    tmp = arr[i]
    # print("====",i,tmp)
    
    for j in range(1,7):
        if i+j >= 100:
            break
        if arr[i + j] > tmp + 1:
            if not moveshortroute(i+j,que,arr,tmp+1):
                arr[i + j] = tmp + 1
                que.append(i+j)
    # print(que)
    
print(arr[-1])