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

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

간단한 BFS 문제다.

큐에는 (현재위치, 주사위를 굴린 횟수)를 저장한다.

 

쉬운 문제라고 생각한다. 

작년까지만 해도 실버 문제만 주구장창 풀었는데 알고리즘을 본격적으로 배운 이후 지금은 골드도 무섭지 않다.

물론 골드 중에도 못푸는 문제는 널리고 널렸지만 그래도 예전처럼 쫄아서 넘기진 않으니ㅋㅋㅋㅋㅋ

지금은 플래 문제들이 큰 벽처럼 보이지만 이것도 공부 열심히해서 벽 부숴봐야겠다.

역시 알고리즘은 재밌어.

 

from collections import deque
n,m = map(int,input().split())

# 해당 index에 도착하면 board[index]로 위치 이동 
board = [i for i in range(101)]

visited = [0]*101

for i in range(n+m):
    a,b = map(int,input().split())
    board[a] = b


def bfs():
    q = deque([(1,0)])
    visited[1] = 1
    while q:
        x, cnt = q.popleft()

        if x == 100:
            return cnt

        for i in range(1,7):
            nx = x + i
            if 1<=nx<=100 and not visited[nx]:
                visited[nx] = 1
                q.append((board[nx],cnt+1))
            

print(bfs())