문제
- 설명:
(0, 0)
부터(n - 1, n - 1)
까지 최단 경로로 이동하라.
풀이
- 도둑루피를 획득하면 소지한 루피가 감소한다. 즉, 가중치를 $-$라고 생각하게 된다.
(0, 0)
부터(n - 1, n - 1)
까지 링크가 잃어버리는 최소 금액이고 모든 가중치가 $-$이기 때문에 가장 큰 경로로 생각하기 쉽다.- 하지만 가중치를 $-$라고 생각하지말고 양수로 생각하면 반대로 동굴의 출구까지의 최단 경로를 구하면된다.
- 양의 가중치가 있는 그래프에서 최단 경로는 Dijkstra로 구할 수 있기 때문에 그대로 적용해준다.
오늘의 회고
- 처음에는 DP인가 했다. 하지만 초록색 옷을 입은 젤다 아니 링크가 상하좌우로 움직이기 때문에 DP로 풀 수가 없었다.
- 하지만 가중치를 양수로 생각하면 그냥 최단경로를 구하는 것이기 때문에 단순히 구현만하면 되었다.
- Python에서 우선순위 큐를 오랜만에(거의 4년..?) 쓰다보니 헷갈렸다.
- 또 구현상 마냥 쉬운 알고리즘은 아니니 중간 중간 막혔다.
- 답은 많이 푸는 것!
Code
# Baekjoon04485.py
import sys
input = sys.stdin.readline
from queue import PriorityQueue
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def solve(t, n):
cave = [list(map(int, input().split())) for _ in range(n)]
pq = PriorityQueue()
visited = [[False] * n for _ in range(n)]
pq.put((cave[0][0], (0, 0)))
ans = 0
while pq.not_empty:
cost, (curr_row, curr_col) = pq.get()
if curr_row == n - 1 and curr_col == n - 1:
ans = cost
break
if not visited[curr_row][curr_col]:
visited[curr_row][curr_col] = True
for row, col in MOVES:
next_row, next_col = curr_row + row, curr_col + col
if (0 <= next_row < n) and (0 <= next_col < n):
if not visited[next_row][next_col]:
pq.put((cave[next_row][next_col] + cost, (next_row, next_col)))
print(f"Problem {t}: {ans}")
t = 1
n = int(input())
while n != 0:
solve(t, n)
t += 1
n = int(input())
PS
- 상하좌우면 무조건 DP가 아니었던 것은 아니었는데(그니까 상하좌우로 탐색하는데도 DP인 경우) 어떤 문제였는지 기억이 안난다 ㅎ 나중에 생각나면 풀고 포스팅하겠다.
'Problem Solving > 항해99' 카테고리의 다른 글
99클럽 코테 스터디 10일차 TIL + Binary Search (0) | 2024.11.07 |
---|---|
99클럽 코테 스터디 9일차 TIL + Tree, 구현 (0) | 2024.11.05 |
99클럽 코테 스터디 7일차 TIL + DFS, Tree (0) | 2024.11.03 |
99클럽 코테 스터디 6일차 TIL + DFS (0) | 2024.11.02 |
99클럽 코테 스터디 5일차 TIL + DP, Sort (0) | 2024.11.01 |