[python]16928번 뱀과 사다리 게임

최소접근 + 이동 문제시에는 대부분 bfs면 맞는거 같다

import sys
from collections import deque
input = sys.stdin.readline
que = deque()
stg = [0 for i in range(101)]   #1차원 배열로 보드판 만들기
vst = [0 for i in range(101)]   #최소 접근을 위해 중복 진입 금지
lad,snake = map(int,input().split())
for i in range(lad):   #사다리 칸 추가
    fst,scd = map(int,input().split())
    stg[fst] = scd
for i in range(snake):  #뱀 칸 추가
    fst,scd = map(int,input().split())
    stg[fst] = scd
que.append((1,0))   #첫칸부터 시작
vst[1] = 1
while que:      #탐색
    cur = que.popleft()
    for i in range(1,7):   #모든 주사위 경우의 수
        x = cur[0]+i
        if 1<=x<101 and not vst[x]:
            if x==100:       #목적지 도달시 주사위 굴린 횟수 출력 후 종료.
                print(cur[1]+1)
                exit(0)
            elif stg[x]:      #뱀,사다리 칸이라면 그 칸 이동
                que.append((stg[x],cur[1]+1))
                vst[stg[x]] = 1
            else:            #일반 칸이면 주사위 칸만큼 이동함
                que.append((x,cur[1]+1))
                vst[x] = 1