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

💡문제접근

• 앞으로 이동할 수 있는 사다리 객체와 뒤로 이동할 수 있는 뱀 객체를 만들고 주사위의 수 1~6까지 돌려 만약 이동한 값이 사다리 객체에 있다면 앞으로 사다리를 타고 이동하고 이동한 값이 뱀 객체에 있다면 뒤로 뱀을 타고 내려가는 것을 구현하면 된다.

💡코드(메모리 : 34308KB, 시간 : 64ms)

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
visited = [False] * 101
ladder = {}
snake = {}
cnt = [0] * 101
for i in range(N):
    x, y = map(int, input().strip().split())
    ladder[x] = y

for i in range(M):
    u, v = map(int, input().strip().split())
    snake[u] = v

def BFS(start):
    queue = deque()
    queue.append(start)
    visited[start] = True
    while queue:
        v = queue.popleft()
        if v == 100:
            print(cnt[v])
            return
        for i in range(1, 7):
            # 주사위의 눈 수(1 ~ 6) + 현재 위치
            next_location = i + v
            # 1 ~ 100 사이의 범위
            if 1 <= next_location <= 100 and not visited[next_location]:
                # 사다리에 존재하는 키 값이면? → 순간이동(앞으로)
                if next_location in ladder.keys():
                    next_location = ladder[next_location]
                # 뱀에 존재하는 키 값이면? → 순간이동(뒤로)
                if next_location in snake.keys():
                    next_location = snake[next_location]
                if not visited[next_location]:
                    queue.append(next_location)
                    visited[next_location] = True
                    cnt[next_location] = cnt[v] + 1


BFS(1)

💡소요시간 : 30m