[Python] BOJ/백준 16928번 뱀과 사다리 게임

[문제]

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

16928번: 뱀과 사다리 게임

 

[풀이]

우와 탐욕법인가 했는데.. 이게··· BFS 문제라니.. 충격과 공포 그자체였음

 

그렇지만!.... 탐색 문제인걸 알기만 하면 문제 푸는건 쉽다 하하

 

1. 사다리와 뱀 dictionary를 만들어 key와 value로 저장한다.
2. deque로 선언한 큐에 처음 출발지인 1을 넣는다.
3. 주사위 숫자인 1부터 6까지 반복문을 돈다.
4. 이동할 칸이 1이상 100이하이고 아직 방문하지 않았다면
   1. snack의 key값에 이동할 칸이 키값으로 있는지 확인
      • 있을 경우 이동할 칸을 snack[next_move] 값으로 교체
   2. ladder의 key값에 이동할 칸이 키값으로 있는지 확인
      • 있을 경우 이동할 칸을 ladder[next_move] 값으로 교체
   3. 위의 if문에서 next_move 값이 교체됐을 수 있으므로 방문 여부를 다시 확인해준다.
      • 방문하지 않았다면
        1. queue에 넣는다.
        2. 해당 칸의 방문 여부를 True로 바꿔준다.
        3. 주사위를 굴린 숫자를 1 추가해준다.

 

[코드]

import sys
from collections import deque


def bfs():
    queue = deque()
    queue.append(1)
    visited[1] = True
    while queue:
        now = queue.popleft()
        for i in range(1, 7):
            next_move = now + i
            if 1 <= next_move <= 100 and not visited[next_move]:
                if next_move in snack.keys():
                    next_move = snack[next_move]
                if next_move in ladder.keys():
                    next_move = ladder[next_move]
                if not visited[next_move]:
                    queue.append(next_move)
                    visited[next_move] = True
                    board_cnt[next_move] = board_cnt[now] + 1


N, M = map(int, sys.stdin.readline().split())
board_cnt = [0] * 101
visited = [False] * 101

snack = dict()
ladder = dict()
for _ in range(N):
    u, v = map(int, sys.stdin.readline().split())
    ladder[u] = v
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    snack[u] = v

bfs()
print(board_cnt[100])