[BaekJoon] 백준 16928번 뱀과 사다리 게임 - Python

[BaekJoon] 백준 16928번 뱀과 사다리 게임 - Python

 

🎈문제

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

16928번: 뱀과 사다리 게임

 

💬설명

• 간단한 bfs문제
• 게임판 전체를 기준으로 주사위 1-6칸이 나왔을 경우를 하나씩 큐에 넣어가면서 해결하면 되는 문제
• 포인트는 사다리나 뱀을 만난 경우 이동하는 칸으로 update를 해줘야 한다는 것이다.

 

👩‍💻코드

from collections import deque


N, M = map(int, input().split())
visited = [False for _ in range(101)]
jump = {}
for _ in range(N + M):
    tmp = list(map(int, input().split()))
    jump[tmp[0]] = tmp[1]

queue = deque([[1, 0]])  # 현재 위치, 주사위 굴린 횟수
visited[1] = True

while queue:
    v = queue.popleft()

    if v[0] == 100:
        print(v[1])
        exit()

    for i in range(1, 7):
        nv = v[0] + i

        if nv > 100:
            continue
        if visited[nv]:
            continue

        if nv in jump:
            nv = jump[nv]
            if not visited[nv]:
                visited[nv] = True
                queue.append([nv, v[1] + 1])
        else:
            visited[nv] = True
            queue.append([nv, v[1] + 1])