백준 16928 뱀과 사다리 게임(BFS)

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

16928번: 뱀과 사다리 게임

 

뱀과 사다리의 좌표가 주어진 것을 활용하기 위해 list의 in 개념을 이용하려고 했지만 비효율적인 것 같아 Dict의 key, value를 이용해서 접근 하기로 했다. 주사위를 굴려서 1~6을 이동하면서 좌표의 cnt를 기억해두는 dp배열을 하나 만들고 저장하기로 했다.

 

유의할점은 뱀과 사다리로 이동하는 것은 주사위를 굴리는 것이 아닌 행동이기 때문에 bfs를 구현할 때 

그냥 주사위로 이동할때만 cnt + 1을 해주는 것이 맞다고 생각했다.

 

from collections import deque

def bfs():
    queue = deque()
    queue.append(1)
    visited[1] = 1

    while queue:
        now = queue.popleft()
        for i in range(1,7):
            temp = now + i

            if 0 < temp <= 100 and not visited[temp]:
                if temp in ladder.keys():
                    temp = ladder[temp]

                if temp in snake.keys():
                    temp = snake[temp]

                if not visited[temp]:
                    queue.append(temp)
                    visited[temp] = 1
                    dp[temp] = dp[now] + 1



n,m = list(map(int,input().split()))
dp = [0] * 101
ladder = dict()
snake = dict()

visited = [0] * 101

for _ in range(n):
    a,b = list(map(int,input().split()))
    ladder[a] = b

for _ in range(m):
    a,b = list(map(int,input().split()))
    snake[a] = b

bfs()
#print(dp)
print(dp[100])