화성탐사

문제

최단경로 챕터에 있어서 사실 다익스트라나 플로이드 워셜을 의도한 것 같지만 내가 푼 방식이 더 마음에 든다 👀

접근 방식

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')