[파이썬] 백준 알고리즘 No.16928 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

 

from collections import deque
n, m = map(int, input().split()) # 사다리, 뱀
a = [[i] for i in range(1, 101)]
visited = [False] * 101
ladder = [[] for _ in range(101)]
snake = [[] for _ in range(101)]

for i in range(n):
    start, end = map(int, input().split())
    ladder[start].append(end)

for i in range(m):
    start, end = map(int, input().split())
    snake[start].append(end)


queue = deque()
queue.append((1, 0))

while queue:
    tmp = []
    x, count = queue.popleft()
    visited[x] = True
    if x == 100:
        print(count)
        exit()

    for i in range(1, 7):
        nx = x + i
        if 0 <= nx <= 100 and not visited[nx]:
            visited[nx] = True
            if ladder[nx]:
                queue.append((*ladder[nx], count + 1))
            if snake[nx]:
                queue.append((*snake[nx], count + 1))
            else:
                queue.append((nx, count + 1))

 

뱀과 사다리를 구분지어 bfs로 100이 나왔을 때 최소되는 count를 반환해준다.

사다리는 무조건 높은 곳에, 뱀은 낮은 곳에 위치하지만

오히려 뱀을 타야지  더 빠르게 갈 수 있는 경우의 수도 있기에 주의깊게 살펴야 한다.