[백준] 16928. 뱀과 사다리 게임 (Python)

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

16928번: 뱀과 사다리 게임

 

🐍 사다리나 뱀을 만나면 위치의 변화가 일어남

🐍 1에서 출발하여 100에 도착하기까지 주사위를 최소로 굴릴 때를 찾는 문제

🐍 간단한 BFS 문제로, 이동한 칸이 사다리나 뱀이 존재하는지 편하게 탐색하기 위해 딕셔너리로 사다리와 뱀의 정보를 저장했다.

 

import sys
from collections import deque

def BFS():
    q = deque()
    q.append((1, 0))
    visit = [0]*101 # 방문 체크
    visit[1] = 1
    while q:
        now, cnt = q.popleft()
        if now == 100: # 100에 도달하면 cnt 출력
            return cnt
        for num in range(1, 7): # 1부터 6까지 주사위
            tmp = now+num
            if tmp <= 100: # 100 초과하면 이동 불가능
                if visit[tmp]: continue # 방문한 적 있으면 이후 로직 처리 X
                if tmp in ladder.keys(): # 사다리 시작 지점에 이동 결과가 있으면
                    visit[tmp] = 1 # 이동 결과에 방문 체크
                    visit[ladder[tmp]] = 1 # 사다리 타고 올라간 곳도 방문 체크
                    q.append((ladder[tmp], cnt+1)) # q에 append
                elif tmp in snake.keys(): # 뱀 시작 지점에 이동 결과가 있으면
                    visit[tmp] = 1 # 이동 결과에 방문 체크
                    visit[snake[tmp]] = 1 # 뱀 타고 내려간 곳도 방문 체크
                    q.append((snake[tmp], cnt+1)) # q에 append
                else:
                    visit[tmp] = 1
                    q.append((now+num, cnt+1))

input = sys.stdin.readline

N, M = map(int, input().split())

ladder = {}
snake = {}

# 추후 탐색을 위해 딕셔너리 형태로 저장
for _ in range(N):
    start, end = map(int, input().split()) # 사다리 시작 지점, 끝 지점
    ladder[start] = end

for _ in range(M):
    start, end = map(int, input().split()) # 뱀 시작 지점, 끝 지점
    snake[start] = end

print(BFS())