BFS - 16928번: 뱀과 사다리 게임

• 모든 간선 가중치가 1 or 동일한 경우 -> BFS
• 양의 가중치 -> 다익스트라
• 가중치가 0 or 1 -> 0-1 BFS(deque 앞, 뒤로 삽입)

from collections import deque, defaultdict

n, m = map(int, input().split())
ladders = defaultdict(int)
snakes = defaultdict(int)

for i in range(n):
    line = list(map(int, input().split()))
    ladders[line[0]] = line[1]

for i in range(m):
    line = list(map(int, input().split()))
    snakes[line[0]] = line[1]


# 1 to 100

def bfs(snakes, ladders):
    q = deque()
    q.append((1, 0))
    visited = set()
    visited.add(1)
    answer = -1

    while q:
        now, turn = q.popleft()

        if now == 100: # 100에 도착 시 종료
            answer = turn
            break

        for i in range(1, 7): # 주사위 1~6
            next = now + i
            
            if next <= 100 and next not in visited: # 다음 칸이 맵 내부이면서 방문 안한 칸이라면
                if next in ladders: # 사다리가 있는 칸이면 해당 칸으로 이동
                    q.append((ladders[next], turn + 1))
                    visited.add(ladders[next])
                elif next in snakes: # 뱀이 있는 칸이면 해당 칸으로 이동
                    q.append((snakes[next], turn + 1))
                    visited.add(snakes[next])
                else: # 아무것도 없으면 다음 칸으로 이동
                    q.append((next, turn + 1))
                    visited.add(next)
    
    return answer

print(bfs(snakes, ladders))