BOJ16928 뱀과 사다리 게임

문제

BOJ16928 뱀과 사다리 게임
실버I | 백준 16928 | Python3 파이썬 풀이

알고리즘

사다리와 뱀은 딕셔너리에 저장해놓는다.
나머지는 BFS를 이용해 모든 칸을 탐색하며 끝 칸에 도착하게 되는 노드의 순서를 출력한다.

코드

import sys
from collections import deque

input = sys.stdin.readline

def BFS():
    queue = deque()
    min_count = 1000000
    curr = 0
    visited[curr] = True
    queue.append([curr, 0])

    while queue:
        curr, count = queue.popleft()

        if curr == 99:
            min_count = min(count, min_count)
            return min_count

        for i in range(1, 7):
            if curr + i < 100:
                if not visited[curr + i]:
                    if curr + i in snake.keys():
                        queue.append([snake[curr + i], count + 1])
                        visited[snake[curr + i]] = True
                    else:
                        queue.append([curr + i, count + 1])
                        visited[curr + i] = True

    return min_count


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

table = [0 for _ in range(100)]
snake = dict()
visited = [False for _ in range(100)]

for n in range(N + M):
    x, y = map(int, input().split())
    snake[x - 1] = y - 1
    
print(BFS())

결과