[백준] 16928번 뱀과 사다리 (파이썬)

난이도 : GOLD V

문제링크 : https://www.acmicpc.net/problem/16928

문제해결 아이디어

• N개의 사다리의 (시작점, 끝점)과 M개의 뱀의 (시작점, 끝점)을 각각 graph에 넣어준다.

• bfs()를 수행하는데, 처음에 1번칸에서 시작하므로 q에 1을 넣고 시작한다.

  • 현재 x번째 칸에서 k값을 더한 x+k가 다음칸이다.

  • 다음 칸에 사다리나 뱀이 존재한다면 다음칸을 ladder나 snake로 바꿔준다.

소스코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

ladder = []

graph = [i for i in range(0, 110)]

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

snake = []

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

ans = []

visited = [0] * 110

q = deque([1])

while q:
    x = q.popleft()

    if x == 100:
        print(visited[x])
        break
    if x > 100:
        break
    for i in range(1, 7):
        target = graph[x + i]
        if not visited[target]:
            visited[target] = visited[x] + 1
            q.append(target)