[Algorithm] 백준 16928 뱀과 사다리게임 python

백준 16928 원문

1. 문제가 뭐였지

10x10의 게임판이 주어진다. 플레이어는 주사위를 굴려서 나온 수 만큼 이동을 해야 하는데, 100번칸을 넘는다면 아예 이동할 수는 없다.

몇 몇 칸에는 사다리 or 뱀이 주어진다. 도착한 칸이 사다리라면 위로 올라가야 하고, 뱀이 있으면 뱀을 따라 내려가야 한다.

1번에서 시작해서 100번칸에 도착해야 하는데, 주사위를 마음대로 조작할 수 있다면 최소 몇번 만에 마지막 칸에 도착하는가가 문제다,.

2. 어떻게 풀었지

특별...한건 없고 그냥 bfs로 풀면 된다.

3. 어디서 해맸지

10x10이니까 이차원 배열 꾸역꾸역 쓸려고 했었는데 사실 큰 의미는 없었다. 그냥 사다리와 뱀을 저장한 배열을 두고, bfs를 돌리면서 풀면 된다.

다른 분들 풀이를 보니까, 아예 dp처럼 배열을 하나 두고 각각의 배열을 1부터 도달할 수 있는 최소 주사위 횟수로 해서 풀었더라.

나는 그냥 큐에다가 (도착지점,주사위 횟수) 이렇게 넣으면서, bfs를 돌릴 때 주사위 횟수를 같이 저장하면서 갔다.

다 쓰고 보니까 굳이 snake, ladder 따로 두지 말고 한번에 관리해도 될 것 같다. 어차피 조건에서 둘이 동시에 있을 수는 없다고 해서

4. Code

"""
사다리는 영어로 ladder
"""

import sys
from collections import deque

input = sys.stdin.readline
   
def solve(n,m) :
    
    snake = [0 for _ in range(101)]
    ledder = [0 for k in range(101)]
    #합쳐서 관리하는게 더 나을 것 같다.
    
    visited = [False for _ in range(101)]

    for i in range(n) :
        x , y = map(int,input().split())
        ledder[x] = y
    
    for j in range(m) :
        x , y = map(int,input().split())
        snake[x] = y

    q = deque()

    q.append((1,0))
    visited[1] = True

    ans = float("inf")

    while q :
        
        front = q.popleft()

        if front[0] == 100 :
            ans = min(ans, front[1])
            continue


        for i in range(1,7) :
            new = front[0]+i
            
            if new > 100 :continue
            
            if visited[new] == True :
                continue
            
            visited[new] = True

            if snake[new] != 0 :
                new = snake[new]
            
            if ledder[new] != 0 :
                new = ledder[new]

            q.append((new,front[1]+1))
    
    print(ans)
        
        
if __name__ =="__main__" :
    n,m = map(int,input().split())
    solve(n,m)