[Python/파이썬] 백준 16928 - 뱀과 사다리 게임

문제 설명

입출력 예제

 

---

풀이 코드

10 x 10 크기의 보드판에서 진행되는 게임이라고 했지만 상하좌우로 움직이는게 아닌, 한 방향으로만 움직일 수 있다.

그렇기 대문에 2차원 배열이 아닌 1차원 배열로 나열해 풀 수 있다.

그리고 주어진 사다리, 뱀의 위치를 dict(딕셔너리) 타입으로 받아 주사위를 던져 도착한곳이 사다리, 뱀 위치(key)면 value로 이동시킨다.

 

정답 코드

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

n, m = map(int, input().split()) # 사다리 수, 뱀 수

board = [0] * 101
visited = [False] * 101

ladder = dict()
for _ in range(n):
    i,j = map(int,input().split())
    ladder[i] = j

snack = dict()
for _ in range(m):
    i,j = map(int,input().split())
    snack[i] = j

def bfs(start):
    q = deque()
    q.append(start)

    visited[start] = True

    while q:
        cur = q.popleft()

        for i in range(1, 7): # 주사위 1 ~ 6
            next = cur + i

            if 0 < next <= 100 and not visited[next]:
                if next in ladder:
                    next = ladder[next]
                
                if next in snack:
                    next = snack[next]
                
                if not visited[next]:
                    q.append(next)
                    visited[next] = True
                    board[next] = board[cur] + 1

bfs(1) # 1부터 시작
print(board[100])