[python] 뱀과 사다리 게임_백준16928번(bfs)

이희진·2023년 3월 28일
0

백준 16928번 - 뱀과 사다리 게임


이 문제는 최소 주사위 횟수를 구해야 하는 bfs 문제이다.
전에는 너비우선탐색을 하며 전의 값 + 1만 해주면 되었다면, 이 문제는 이 값이 뱀이나 사다리가 있는지에 따라 경우가 추가되는 문제다.
그래서 visited 정보를 따로 저장해주었고, board에는 0으로 초기화한 후, 뱀과 사다리 위치에는 연결되는 ㄱ값을 넣어주었다. 하나씩 방문해가면서 0이 아닌 경우는 뱀과 사다리로 처리하고, 0인 경우는 일반적인 너비우선탐색으로 처리했다.

solution

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

def solve():
    global board, visited
    visited[1] = True
    queue = deque([1])
    while queue:
        x = queue.popleft()
        for i in range(1, 7):
            if visited[x + i] == False:
                if board[x + i] == 0:
                    board[x+i] = board[x] + 1
                    visited[x+i] = True
                    if x+i == 100:
                        return board[100] 
                    queue.append(x+i)
                else:
                    next = board[x+i]
                    if visited[next] == False:
                        board[next] = board[x] + 1
                        visited[next] = True
                        queue.append(next)

n, m = map(int, input().split(' '))
board = [0] * 101
visited = [False] * 101
for _ in range(n):
    x, y = map(int, input().split(' '))
    board[x] = y
for _ in range(m):
    x, y = map(int, input().split(' '))
    board[x] = y

print(solve())

0개의 댓글