[백준]16928(파이썬) - 뱀과 사다리 게임
resilient
·2021. 12. 29. 00:01
728x90
반응형
https://www.acmicpc.net/problem/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로 풀어야겠다는 확신을 가진 나머지, 다른 방법을 생각하지 못했습니다. 좀 더 유연한 사고를 가져 볼 수 있는 좋은 문제였다고 생각합니다.
반응형
'자료구조 & 알고리즘 > 백준(Baekjoon)' 카테고리의 다른 글
[백준]2206(파이썬) - 벽 부수고 이동하기 (0) | 2022.01.04 |
---|---|
[백준]21610(파이썬) - 마법사 상어와 비바라기 (0) | 2021.12.31 |
[백준]14891(파이썬) - 톱니바퀴 (0) | 2021.12.09 |
[백준]14503(파이썬) - 로봇청소기 (6) | 2021.12.06 |
[백준] 14501(파이썬) - 퇴사 (0) | 2021.12.03 |