[BOJ / Python] 16928번 : 뱀과 사다리 게임

문제 제목, 난이도

16928번 : 뱀과 사다리 게임, 실버1

---

문제 링크

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

---

코드(Python)

# 뱀과 사다리
import sys
from collections import deque

input = sys.stdin.readline

board = []
visited = [False] * 110
for i in range(0,110) :
    board.append([i,i])

n, m = map(int,input().split())
for _ in range(n+m) :
    x, y = map(int,input().split())
    board[x][1] = y

li = deque([[1,0]])

def roll(cur) :
    for i in range(1,7) :
        temp = board[cur[0]+i][1]
        count = cur[1] + 1
        if visited[temp] == False :
            li.append([temp,count])
            visited[temp] = True

while True :
    cur = li.popleft()
    if cur[0] == 100 :
        print(cur[1])
        break
    else :
        roll(cur)

---

풀이

110 x 110 보드 (형식 : [출발점, 끝점])를 생성합니다. (99번째 칸에서 2칸 이상 이동시 인덱스 오류 발생 가능성)

 

뱀과 사다리 개수는 중요하지 않아서 더한 뒤 한 번에 입력받았습니다.

 

li라는 이름의 deque 생성 (형식 : [위치, 주사위 굴린 횟수])

 

주사위를 한 번씩 굴린 뒤 방문하지 않았으면 li에 append

 

li는 자연스럽게 [ (한번 굴린 경우들) , (두 번 굴린 경우들) , ... ] 로 구성됨

 

100에 도달 시 프린트 문 실행 후 종료

---

체크리스트

BFS, 완전탐색

방문했었는지 확인하지 않아서 처음에 시간 초과 발생

이 문제에서는 주사위를 덜 굴린 순서대로 방문하고 있기 때문에 몇 번째만에 도착하는지는 확인하지 않아도 괜찮다.