[백준] 16928번 문제, 뱀과 사다리 게임

알고리즘

뱀과 사다리 게임을 코드로 구현하는 문제로 1에서 출발해 100에 도달할 때 최소 이동 수를 출력하면 된다.
사다리 개수 N과 뱀 개수 M을 입력 받고 그 개수 만큼의 좌표를 입력 받아 N_position과 M_position에 딕셔너리 형태로 저장한다.(탐색 시간 O(1))
그런 다음에 1부터 +1~+6을 BFS로 탐색하며 빠르게 100에 도달하면 된다. 그리고 1과 100에는 뱀과 사다리가 없기 때문에 무조건 주사위를 굴려서 가야 한다. 따라서 주사위 값을 더하는 부분에서 100이면 return을 통해 탐색을 중단시킨다.

코드

import sys
from collections import deque

IN = sys.stdin.readline

if __name__ == "__main__":
    N, M = map(int, IN().split())
    N_position = {}
    M_position = {}

    # input
    for _ in range(N):
        k, v = map(int, IN().split())

        N_position[k] = v
    for _ in range(M):
        k, v = map(int, IN().split())

        M_position[k] = v

    # bfs
    def bfs():
        que = deque([(1, 0)])
        visited = [False for _ in range(101)]
        visited[1] = True

        while que:
            now_num, now_cost = que.popleft()

            # 주사위 굴리기
            for x in range(1, 7):
                next_num = now_num + x

                if next_num == 100:
                    return now_cost + 1
                elif next_num < 100 and not visited[next_num]:
                    N_trigger = N_position.get(next_num, -1)
                    M_trigger = M_position.get(next_num, -1)

                    if N_trigger != -1:
                        next_num = N_trigger
                    elif M_trigger != -1:
                        next_num = M_trigger

                    if not visited[next_num]:
                        visited[next_num] = True
                        que.append((next_num, now_cost + 1))

    print(bfs())