[백준] 16928 파이썬(python) : 뱀과 사다리 게임 - (★)

16928번: 뱀과 사다리 게임

 

 

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [ i for i in range(100+1) ] #1
for _ in range(n+m): #2
    a, b = map(int, sys.stdin.readline().split())
    graph[a] = b
visited = [0] * (101) #3

def bfs():
    q = deque()
    q.append(1)
    while q:
        now = q.popleft()
        for i in range(1, 6+1): #4
            next = now + i #5
            if next > 100: #6
                continue
            ladder = graph[next] #7
            if visited[ladder] == 0: #8
                visited[ladder] = visited[now] + 1 #9
                q.append(ladder)
bfs()
print(visited[100])

 

graph에 눈금과 사다리 및 뱀 이동을 모두 표시하고, 이동 횟수는 visited에 기록함을 유의하면서 코드를 읽어야 한다!

#1 : 그래프로 게임판의 숫자(눈금)을 표기

#2 : 사다리와 뱀은 서로 곂치지 않기 때문에 같이 묶어서 입력

#3 : 0이면 미방문 0이 아니면 최소 방문횟수

#4 : 주사위니까 1~6까지 반복

#5 : 주사위 던지고 움직인 숫자(인덱스)

#6 : 100 넘으면 continue

#7 : 주사위 던지고 움직인 숫자 값, 만일 사다리나 뱀이라면 그만큼 움직이고 아니라면 게임칸의 위치가 된다.

#8 : 미방문 상태일때

#9 : 현재눈금 값 + 1 = 다음눈금 값

 

어려웠다. 2개의 입력값을 받아서 계산하는 일반적인 그래프 문제가 아니라서 큐에 넣었다 뺐다하는 bfs를 어떻게 적용해야할지 감이 잡히지 않았다. 확실히 실버1과 골드5는 난이도 차이가 많이 나는것 같다.