백준 파이썬 16928 뱀과 사다리 게임

백준 링크 : https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

1부터 100까지 가는 수단중 가장 최솟값을 구하는 문제이다.

 

보통 최소값? 가는 경로??? 하면 다익스트라 OR BFS인데 여기선 BFS로 해도 괜찮을 거라고 판단 + 이게 더 쉬울거라고 생각해서 BFS로 풀이했다.

 

from collections import deque

s = [-1 for i in range(101)]

visited=[i for i in range(101)]

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

for i in range(n):
    a,b=map(int,input().split())

    visited[a] = b

for i in range(m):
    a,b=map(int,input().split())

    visited[a] = b

queue = deque()
queue.append(1)

s[1] = 0

while queue:
    x = queue.popleft()

    for i in range(1,7):
        y = x+i
        if (y>100):
            continue
        y = visited[y]
        if (s[y] == -1 or s[y]>s[x]+1):
            s[y] = s[x]+1
            queue.append(y)

print(s[100])

-1로 방문하지 않음을 표시하는 s

visited 변수에 뱀과 사다리 변수를 집어 넣어서 점프할 거리를 재어준 후

계속해서 비교하면 되는 간단한 BFS문제