[백준/파이썬] 16928번: 뱀과 사다리 게임

문제

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

풀이

• 주사위를 조작해 원하는 수가 나오게 만들 때, 최소 몇 번만에 도착점에 도착하는가?
• 주사위: 1~6
• 보드판: 10×10
• 주사위를 굴려 나온 수만큼 이동
  • 사다리가 있는 칸: 사다리를 타고 위로 이동
  • 뱀이 있는 칸: 뱀을 따라 아래로 이동
  • 1번 칸에서 시작 -> 100번 칸에 도착

이 문제는 1번 칸에서 시작해서 100번 칸에 도착하는 최단 경로를 탐색하는 문제입니다.

BFS를 사용해 풀었습니다.

우선 게임판은 100칸으로만 설정해두었습니다.
문제만 본다면 2차원 배열로 선언해야될 것 같지만, 0번 칸에서 100번 칸으로 이동하는 최단 경로만 탐색하면 되기 때문이죠

    board = [0] * 101 # 게임판
    
    # 사다리
    for _ in range(n):
        x,y = map(int,input().split())
        board[x] = y # x칸에 도착하면 y칸으로 이동
    
    # 뱀
    for _ in range(m):
        u,v = map(int,input().split())
        board[u] = v # u칸에 도착하면 v칸으로 이동

게임판의 좌표도 모두 설정했으니 탐색을 시작해볼게요 👊

시작하려는 칸(1번)과 주사위를 굴린 횟수(0회)를 queue에 담아 줍니다.
한 번 방문한 칸을 다시 방문하게 되면 최단 경로가 아니게 되므로 방문 여부를 알 수 있는 visited도 선언했습니다.

def bfs(board):
    visited = [False] * 101 # 방문 여부
    queue = deque([(1,0)]) # 시작 지점, 주사위 횟수
    visited[1] = True # 방문 처리

우선 좌표를 추출하고 이 값을 이용해 주사위를 굴려보겠습니다.

    while queue:
        loc, cnt = queue.popleft()
        if loc == 100: # 100이면 도착이므로 주사위 횟수 리턴
            return cnt

주사위는 1부터 6까지 수를 제 마음대로 설정할 수 있으므로, 반복문 범위를 1부터 6까지 설정해줍니다.

주사위를 굴려 나온 수들을 모두 탐색하여 줍니다.

        for d in range(1,7):
            next_loc = loc + d # 다음 좌표
            if next_loc > 100: # 100 이상이면 pass
                continue
            
            if board[next_loc] != 0: # 뱀 or 사다리일 경우
                next_loc = board[next_loc] # 좌표 변경
            
            if not visited[next_loc]: # 방문하지 않은 좌표일 경우
                visited[next_loc] = True # 방문 처리
                queue.append((next_loc, cnt + 1)) # 다음 좌표 탐색

이렇게 모든 좌표를 탐색하게 되면 최단 거리를 찾을 수 있습니다 🥳

코드

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

def bfs(board):
    visited = [False] * 101
    queue = deque([(1,0)])
    visited[1] = True
    
    while queue:
        loc, cnt = queue.popleft()
        if loc == 100:
            return cnt
        
        for d in range(1,7):
            next_loc = loc + d
            if next_loc > 100:
                continue
            
            if board[next_loc] != 0:
                next_loc = board[next_loc]
            
            if not visited[next_loc]:
                visited[next_loc] = True
                queue.append((next_loc, cnt + 1))

if __name__ == "__main__":
    n,m = map(int,input().split())
    board = [0] * 101
    
    for _ in range(n):
        x,y = map(int,input().split())
        board[x] = y
    
    for _ in range(m):
        u,v = map(int,input().split())
        board[u] = v
    
    print(bfs(board))