최단경로 챕터에 있어서 사실 다익스트라나 플로이드 워셜을 의도한 것 같지만 내가 푼 방식이 더 마음에 든다 👀
BFS + DP를 활용했다.
문제는 (0, 0)에서 (n-1, n-1)로 가는 최단 비용을 물어보고 있다.
단순 BFS로 접근하면 해당 위치의 비용을 고려하지 않고 최단 경로를 구할 순 있을 것이다. 다만 여기서 해당 위치의 비용을 계산해야 하기 때문에, 주어진 그래프와 같은 DP를 만들어서 해당 위치까지의 최소 비용을 관리해야 한다.
최근에 푼 백준 6087에서 아이디어 힌트를 얻었다 -> 풀이
from collections import deque
INF = int(1e9)
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def move():
n = int(input())
space = [list(map(int, input().split())) for _ in range(n)]
dp = [[INF] * n for _ in range(n)] # 최소 비용 저장
queue = deque([(0, 0, space[0][0])]) # x, y좌표, 현재 비용
while queue:
cx, cy, cost = queue.popleft()
for dx, dy in dirs:
if 0 <= cx + dx < n and 0 <= cy + dy < n and cost + space[cx + dx][cy + dy] <= dp[cx + dx][cy + dy]:
dp[cx + dx][cy + dy] = cost + space[cx + dx][cy + dy]
queue.append((cx + dx, cy + dy, cost + space[cx + dx][cy + dy]))
return dp[n-1][n-1]
T = int(input())
res = []
for _ in range(T):
res.append(move())
print(*res, sep='\n')