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

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

16928번: 뱀과 사다리 게임

 

# 조건

• 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을지 구하라
• 크기가 10x10이고 총 100개의 칸으로 나누어져 있다.
• 플레이어가 i번 칸에 있고, 나온 수가 4라면, i+4번으로 이동해야한다.
• 결과가 100번을 넘어간다면 이동할 수 없다.
• 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다.
• 뱀이 있는 칸에 도착하면, 뱀을 따라 내려간다.
• 사다리의 수 N개, 뱀의 수 M개

 

# 접근 방법

• 사다리 리스트를 받아주고 뱀의 위치를 기록해준다.
• 모든 칸에 몇 번만에 갈 수 있는 지를 bfs를 이용해서 기록해준다.
• deque를 이용해 주사위 경우의 수 체크해주면 될 것같다.
• 사다리를 타고 올라가는 경우, 뱀을 타고 내려오는 경우를 생각해주어야 한다.
• 딕셔너리를 이용해, 사다리와 뱀의 도착 지점을 기록해준다.
• dp를 이용하여 도착하는 경우의 수 중 최솟값을 기록해주어도 되지만 bfs로 풀릴 것 같으므로 pass

 

# BFS 이용 내 풀이

import sys  
sys.stdin = open('input.txt')  
from collections import deque  
  
  
  
def board_check(num):  
    q = deque()  
    q.append(num)  
    while q:  
        sti = q.popleft()  
        for i in range(1,7):  
            # 현재 위치에서 주사위를 던져 갈 수 있는 위치  
            loc = sti+i  
            # 방문 기록 -> 이미 방문하였다면 현재 가는 횟수는 최소가 아니다.  
            if loc < 101 and visited[loc] == 0:  
                # 사다리 또는 뱀이 있는 경우  
                # 갈 수 있는 위치를 변경 해준다.               
                if loc in ladder:  
                    loc = ladder[loc]  
                if loc in snake:  
                    loc = snake[loc]  
                # 이동할 위치가 방문하지 않았다면 +1 및 추가  
                if visited[loc] == 0:  
                    visited[loc] = visited[sti] +1  
                    q.append(loc)  
  
  
N, M = map(int, input().split())  
  
board = [0] * 101  
visited= [0] * 101  
  
ladder, snake = {}, {}  
  
for _ in range(N):  
    x,y = map(int, input().split())  
    ladder[x] = y  
  
for _ in range(M):  
    x, y = map(int, input().split())  
    snake[x] = y  
  
board_check(1)  
print(visited[100])