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

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

16928번: 뱀과 사다리 게임

 

이 문제는 처음에 DP로 풀었다가 결국에는 BFS로 풀게 된,,, 시간이 꽤 오래 걸렸던 문제입니다.

 

• 이 문제를 처음 읽고 든 생각은 'DP로 풀어야겠다' 였습니다.
• 먼저, Bottom-up 방식을 이용, 1차원 DP 테이블을 만들어 준 뒤, 사다리( 위로 올라가는 칸) 만을 고려해서 DP테이블을 갱신했습니다.
• 두 번째로,  for문을 한 번 더 돌면서 뱀( 아래로 내려오는 칸) 을 구현 했고, 다시 Bottom-up을 사용하기 위해서 사다리( 위로 올라가는 칸)을 구현해 주는 일종의  cycle을 만들어줬습니다.
• 하지만 22프로에서 계속 틀렸고 결국엔 다른 방법을 찾아야 했습니다. ( 혹시 DP로 푸는 방법을 아시는 분은 댓글 달아주시면 감사하겠습니다! ㅠㅠ )

 

import sys
input = sys.stdin.readline
from collections import defaultdict
# dp[i][j] = i 번째 칸에 j 번의 주사위를 굴려서 올 수 있나? → T,f

dp = [0] * 101
INF = 1000000000
snakeDict, ladderDict = defaultdict(), defaultdict()

n, m = map(int, input().split())

for i in range(n):
    start, end = map(int , input().split())
    ladderDict[start] = end
for i in range(m):
    start, end = map(int , input().split())
    snakeDict[start] = end
re_ladder = {v:k for k,v in ladderDict.items()}
re_snake = {v:k for k,v in snakeDict.items()}
dp[1] = 0
dp[2], dp[3], dp[4], dp[5], dp[6], dp[7] = 1,1,1,1,1,1

print(re_snake)
for i in range(8, 101): 
    dp[i] = INF
for i in range(8, 101):
    # 뱀이 현 위치에서 내려가는 것
    if i in re_ladder:
    # 사다리는 현 위치에서 올라가는 것
        dp[i] = min(dp[i-6]+1,dp[i-5]+1, dp[i-4]+1, dp[i-3]+1, dp[i-2]+1 , dp[i-1]+1, dp[re_ladder[i]])
    else:
        dp[i] = min(dp[i-6]+1,dp[i-5]+1, dp[i-4]+1, dp[i-3]+1, dp[i-2]+1 , dp[i-1]+1)
for i in range(8,101):
    if i in re_snake:
        dp[i] = min(dp[i],dp[re_snake[i]])
    if i in re_ladder:
    # 사다리는 현 위치에서 올라가는 것
        dp[i] = min(dp[i],dp[i-6]+1,dp[i-5]+1, dp[i-4]+1, dp[i-3]+1, dp[i-2]+1 , dp[i-1]+1, dp[re_ladder[i]])
    else:
        dp[i] = min(dp[i], dp[i-6]+1,dp[i-5]+1, dp[i-4]+1, dp[i-3]+1, dp[i-2]+1 , dp[i-1]+1)
print(dp)
print(dp[100])

 

• BFS로 구현하는 방법은 간단합니다.
• 먼저 1부터 100이 담긴 1차원 리스트를 만들어 준 뒤, 최단 거리를 구하는 방식으로 구현하면 됩니다.
• 1차원 리스트를 만들 때 주의 할 점은, 각 칸에 도착했을 때, 사다리나 뱀의 시작점이 있다면 시작점 정보를 끝점 칸의 정보로 변경 해놔야 모든 상황을 고려해서 최단거리로 100에 도달하는 법을 구현 할 수 있습니다.
• 각 칸을 이동할 때, 거리가 담기는 visited라는 리스트를 만들어서 이동할 때마다 1씩 더해서 최단거리를 구해주면 됩니다.

 

import sys
from collections import deque

input  = sys.stdin.readline

n,m = map(int,input().split())
graph = [i for i in range(101)]
for _ in range(n):
    a,b = map(int,input().split())
    graph[a] = b
for _ in range(m):
    a,b = map(int,input().split())
    graph[a] = b
visited  = [0 for _ in range(101)]


def bfs():
    q = deque()
    q.append(1)
    visited[1] = 1
    while q:
        x = q.popleft()
        for i in range(1,7):
            nx = x + i
            if nx > 100:
                continue
            kan = graph[nx]
            if visited[kan] == 0:
                q.append(kan)
                visited[kan] = visited[x] + 1
                if kan == 100:
                    return

bfs()
print(visited[100]-1)

 

 

이 문제는 처음에 DP로 풀어야겠다는 확신을 가진 나머지, 다른 방법을 생각하지 못했습니다. 좀 더 유연한 사고를 가져 볼 수 있는 좋은 문제였다고 생각합니다.