백준 16928 뱀과 사다리 게임

https://www.acmicpc.net/problem/16928

 

 

1부터 시작해서 100까지 가기 위한 주사위 굴리는 횟수의 최솟값을 구하는 문제이다. 이 문제는 그냥 단순히 BFS로 풀면 풀린다. 최단거리를 구하기 위해 각 칸마다 비교를 하며 풀 필요 없다. BFS에서 큐의 먼저 나온 값들이 더 작게 나올 것이라고 생각하면 된다. 그리고 사다리나 뱀을 만나면 무조건 도착칸으로 가기 때문에 시작칸을 큐에 안 넣어야 된다. 그리고 필자는 시작을 0부터 해서 몇 번 틀렸기에 시작을 1부터 해야한다도 상기한다. 몇몇 요소를 조심하며 BFS로 풀면 코드는 아래와 같다

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

L,S=map(int,(input().rstrip()).split())
ladder=dict()

array=[0 for i in range(101)]#값 저장

for _ in range(L+S):
    a,b=map(int,(input().rstrip()).split())
    ladder[a]=b

l_key=ladder.keys()#사다리,뱀 시작칸 
que=deque()
que.append(1)

while que:
    ima=que.popleft()
    for i in range(1,7):#주사위1~6굴리기
        new=ima+i
        if new>100:#값이 벗어나면 건너뛰기
            continue
        if new in l_key:#사다리,뱀이라면 도착칸만 생각
            new=ladder[new]
        if array[new]==0:#미방문
            array[new]=array[ima]+1
            que.append(new)

print(array[100])