문제

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

풀이

BFS 알고리즘을 사용해서 푸는 문제이다.

우선 그래프를 딕셔너리로 선언해주고 1~100까지의 수를 key로, 키와 동일한 수를 value로 초기화 시켜주었다.

이후에 사다리와 뱀의 정보를 입력 받고, 그 정보를 바탕으로 그래프를 수정해주었다.

마지막으로 BFS 함수를 이용해서 구하고자 하는 최소 횟수를 구했다.

import sys
from collections import deque
input = sys.stdin.readline

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

graph = {}

for i in range(1,101):
    graph[i] = i

for i in range(n + m):
    x,y = map(int,input().split())
    graph[x] = y

def bfs(graph):
    queue = deque()
    queue.append((1,0))
    result = -1
    visited = [0 for i in range(101)]
    while queue:
        cur, cnt = queue.popleft()
        for i in range(1,7):
            if cur + i > 100:
                continue
            next = graph[cur + i]
            
            if next == 100:
                result = cnt + 1
                break
            if visited[next] == 1:
                continue
            queue.append((next,cnt + 1))
            visited[next] = 1
        if result != -1:
            break
    return result

print(bfs(graph))