Python 16928번 뱀과 사다리 게임

 

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

16928번: 뱀과 사다리 게임

 

문제를 어떻게 풀까 고민하다가 dp랑 bfs를 섞어서 써봤다!

먼저 visited로 dp를 관리했고 bfs로 주사위를 던져서 간 칸의 값을 q에 append해줬다.

하지만 그 칸에 뱀이나 사다리를 타는 칸이 있다면 사다리를 타고 올라간 칸이나 뱀을 타고 내려간 칸을 dp방식을 이용해 주사위를 던진 횟수가 최소가 되는 경우를 해당 칸의 visited에 저장했다.

처음에는 사다리만 타고 올라가면 최소가 되겠지 생각하고 뱀을 타고 내려간 경우를 안해줬는데

생각해보니 뱀을 타고 내려갔다가 사다리를 타고 올라간 경우가 최소가 되는 경우도 있는 것 같다

예를 들어 사다리를 타고 2번째에서 50번째로 가고 뱀을 타고 가서 52에서 35로 가고 사다리를 다시 또 타서 36에서 100으로 갈 수도 있는 경우도 있다.

import sys
from collections import deque

input=sys.stdin.readline
n,m = map(int,input().split())
ladder={}
snake={}
for i in range(n):
    a,b = map(int,input().split())
    ladder[a]=b
for i in range(m):
    a, b = map(int, input().split())
    snake[a] = b

visited=[10000 for _ in range(101)]
visited[1]=0
check=[0 for _ in range(101)]
def bfs(visited,check):
    q = deque([1])
    check[1]=1
    while True:
        if not q:
            break
        num = q.popleft()
        check[num] = 1
        for c in range(6,0,-1):
            if num+c <=100 and not check[num+c]:
                n_num = num+c
                if n_num in ladder:
                    l_num = ladder[n_num]
                    if not check[l_num]:
                        check[l_num]=1
                        visited[l_num]=min(visited[num]+1,visited[l_num])
                        q.append(l_num)
                        # print(num,n_num,l_num)
                    continue
                if n_num in snake:
                    s_num = snake[n_num]
                    if not check[s_num]:
                        check[s_num]=1
                        visited[s_num]=min(visited[num]+1,visited[s_num])
                        q.append(s_num)
                        # print(num, n_num, s_num)
                    continue
                if visited[num]+1 < visited[n_num]:
                    visited[n_num]=min(visited[num]+1,visited[n_num])
                    q.append(n_num)



bfs(visited,check)
print(visited[100])