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

백준 16928번

✔️ 문제 풀이

◾ bfs 탐색 활용

• ladder와 snake는 딕셔너리를 활용하여 값을 입력받는다
• bfs탐색에서 주사위의 눈만큼 인덱스를 더해가며,
  1) 인덱스가 ladder에 속하는지 검사
  2) 인덱스가 snake에 속하는지 검사
  해서 해당하는 값에 따라 index를 업데이트
  (여기서 혹시 snake로 이동한 칸에 ladder가 연결되어 있으면 어떡하지?! 하고 잠시 고민했지만, 문제 조건에서 한 칸은 하나의 snake or ladder만 갖는다고 되어있다)
• visited[index]가 방문한 적 없는 곳이면, visited[location]+1로 값을 업데이트 해주고, queue에 index 값을 더해준다.
• 이를 visited[100]의 값이 업데이트 될 때까지 반복

최종 제출 코드

import sys
from collections import deque

input = sys.stdin.readline

l, s = map(int, input().split())
visited = [0]*101

ladder = dict()
snake = dict()

for _ in range(l):
  key, value = map(int, input().split())
  ladder[key] = value

for _ in range(s):
  key, value = map(int, input().split())
  snake[key] = value

def bfs():

  queue = deque()
  queue.append(1)

  while not visited[100]:

    location = queue.popleft()

    for i in range(1, 7):
      index = location+i
      if index in ladder:
        index = ladder[index]
      if index in snake:
        index = snake[index]
      if index <= 100 and visited[index] == 0:
        visited[index] = visited[location]+1
        queue.append(index)

  return visited[100]

print(bfs())