백준[16928] 뱀과 사다리 게임 (Python3)

테스트케이스 짜보는 연습해 보기 좋은 문제

완전 탐색

현재 지점부터 +1 ~ +6까지의 지점을 갔을 때에 대한 결과를 큐에 넣고, 100이 될 때까지 탐색한다.
하지만, 뱀을 만나게 되면 다시 돌아가게 돼서 그 지점부터 탐색이 계속 진행되기 때문에
무한 루프가 된다.

완전 탐색 최적화

1에서 7을 가는 최단 경로는 주사위 6이 나와서 이동하는 경우다.
그 외의 방법으로 가는 경우는 비효율적이므로 배제한다.
따라서, 방문 처리 배열을 하나 만들어 이동할 지점에 도달하기 위해 굴린 주사위 수가
현재 굴린 주사위 수 + 1보다 크면 큐에 현재 정보를 추가한다.

주의해야 할 점

사다리를 탈 때 무작정 이 사다리가 더 높이 간단 이유로, 그 사다리만 골라서 가면 안 된다.
뱀을 통해 내려간 곳 근처에 있는 사다리가 더 높은 곳으로 올라갈 수 있다.
(테스트 케이스 만들 때, 뱀은 탈 필요가 없다 생각했다 2번 틀렸다..)

테스트케이스들

3 7
2 40
3 60
42 99
95 13
97 25
93 37
79 27
75 19
49 4
67 17
답 : 3

2 7
2 96
3 93
95 13
97 25
93 37
79 27
75 19
49 47
67 17
답 : 2

1 7
2 3
95 13
97 25
93 37
79 27
75 19
49 47
67 17
답 : 17

4 7
2 40
3 60
21 99
53 99
95 13
61 20
93 37
79 27
75 19
49 47
67 17
답 : 4

 

코드

from collections import deque
N, M = map(int, input().split())
board = list(range(0, 101))
visit = [float("inf")] * 101
visit[1] = 0
for i in range(N + M):
    x, y = map(int, input().split())
    board[x] = y

q = deque([(1, 0)])
while q:
    here, hereC = q.popleft()
    for i in range(1, 7):
        there = here + i
        if there > 100:
            break
        if visit[there] > hereC + 1:
            q.append([board[there], hereC + 1])
            visit[there] = hereC + 1
print(visit[-1])