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

<문제>

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

16928번: 뱀과 사다리 게임

<시간 복잡도>

<코드>

from collections import deque

n, m = map(int, input().split())
graph = [0 for _ in range(101)]
visited = [False] * 101

ladder = {}
snake = {}
for _ in range(n):
    x, y = map(int,input().split())
    ladder[x] = y

for _ in range(m):
    u, v = map(int,input().split())
    snake[u] = v

def bfs():
    q = deque([1])
    visited[1] = True
    while q:
        x = q.popleft()
        for i in range(1,7):
            nx = x + i
            if 0 < nx <= 100 and not visited[nx]:
                if nx in ladder.keys():
                    nx = ladder[nx]
                elif nx in snake.keys():
                    nx = snake[nx]
                if not visited[nx]:
                    q.append(nx)
                    visited[nx] = True
                    graph[nx] = graph[x]+ 1

bfs()
print(graph[100])

<해설>

bfs 기본적인 사고의 시작
1. 하나하나 범위를 넓이며 진행한다.
2. 방문한 곳은 방문처리하고 방문했던 곳은 다시 가지 않는다.

기본적으로 이 두가지를 생각하며 bfs 문제를 해결하는 거 같다. 위의 방식으로 해결을 하면서
이문제의 특이점으로는 사다리와 뱀의 저장에 대한 방식으로 dict를 사용했다는 것이다.
움직일때마다 하나씩 graph 에 움직인 수를 저장하는 방식을 진행하며 해결을 했다.