[BOJ] 16928. 뱀과 사다리 게임

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

문제: 뱀과 사다리 게임에서 주사위를 최소로 굴려 1부터 100까지 가장 빠르게 도착할 수 있게 하라.

 

문제 이해하기!!

뱀과 사다리 게임은 예전에 많이 해봤던 추억의 놀이죠.

그래서 문제를 쉽게 이해할 수 있었던 것 같습니다.

1부터 100까지이므로 모든 경우의 수를 다 확인하면 됩니다 ㅎㅎ (완전탐색!!)

다만, 주의할 점은 뱀으로 이동하면 100번까지 더 빨라지는 경우가 있으므로 사다리만 타지 않도록 주의하셔야 합니다.

 

제가 푼 방식을 설명하자면,

1. 입력을 받아 딕셔너리 형태로 저장해주시구요.

2. 스택을 통해 DFS로 완전탐색을 진행합니다.

3. 1 ~ 6의 숫자가 나왔다는 가정들을 모두 스택에 담아요.

4. 여기서 주의 점은 1 ~ 6의 숫자가 나왔다고 하는 가정을 모두 담으면 범위를 벗어나거나 최소 수를 못 구할 수 있으므로 여러 조건을 걸어주셔야 합니다. 첫 번째는 지금까지 확인했던 숫자의 최소 주사위 수가 최소가 맞는지, 두 번째는 각 숫자에 최소 주사위 횟수를 저장해 놓는데, 저장해 놓는 배열의 인덱스가 벗어나지 않는지입니다. 둘을 조건걸어주고 DFS의 종료조건을 걸어주면 답이 나오게 됩니다.

 

코드:

from sys import stdin
input = stdin.readline


N, M = map(int, input().split())
dic = dict()

for i in range(N):
    a, b = map(int, input().split())
    dic[a] = b

for i in range(M):
    a, b = map(int, input().split())
    dic[a] = b

res = 1
S = [(1, 0)]
can = [float('inf')] * 101
can[1] = 0
while S:
    tmp, cnt = S.pop()
    if tmp >= 100:
        if can[100] > cnt:
            can[100] = cnt
        continue
    for i in range(1, 7):
        if dic.get(tmp+i):
            if can[dic.get(tmp+i)] > cnt + 1:
                can[dic.get(tmp+i)] = cnt + 1
                S.append((dic.get(tmp+i), cnt+1))
        else:
            if tmp + i < 101 and can[tmp + i] > cnt + 1:
                S.append((tmp + i, cnt + 1))
                can[tmp + i] = cnt + 1

print(can[100])