보급로

T = int(input())
import heapq

for test_case in range(1, T + 1):
    N = int(input())
    graph = [[] for _ in range(N)]
    distGraph = [[float('inf') for _ in range(N)] for _ in range(N)]
    answer = -1

    for i in range(N):
        tmp = list(map(int, input()))
        for t in tmp:
            graph[i].append(t)

    # Dijkstra
    start = [0, 0, 0]
    q = [start]
    distGraph[0][0] = 0

    while q:
        curItem = heapq.heappop(q)
        curRow, curCol, dist = curItem[0], curItem[1], curItem[2]

        dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

        if curRow == N - 1 and curCol == N - 1:
            answer = dist
            break

        if dist > distGraph[curRow][curCol]:
            continue
        for xx, yy in zip(dx, dy):
            nxtRow, nxtCol = curRow + xx, curCol + yy
            if 0 <= nxtRow < N and 0 <= nxtCol < N:
                newDist = dist + graph[nxtRow][nxtCol]
                if newDist < distGraph[nxtRow][nxtCol]:
                    distGraph[nxtRow][nxtCol] = newDist
                    heapq.heappush(q, [nxtRow, nxtCol, newDist])

    print("#" + str(test_case) + " " + str(answer))

[D4] 전형적인 BFS 문제라고 생각했다. 여기서 조금 변형을 주어야 한다는 점을 일찍 깨닫고 Dijkstra 로 바로 갔어야 했는데, 그러지 못했던 점이 조금 아쉽다.

길의 중복은 상관없고 무조건 도착점에 작은 가중치의 합으로 도달해야 하므로
visited 배열은 사용하지 않고, 큰 값으로 가득 차 있는 새로운 그래프를 만들어 값을 갱신하는 식으로 이어가는 로직이 필요하다.

BFS에 세 가지 [row, col, 누적 dist] 를 다 가지고 다니면서 로직을 처리하면 너무 많은 불필요한 정보를 처리하게 되므로 메모리 초과나 시간초과가 뜰 가능성이 크기 때문에 Dij 알고리즘으로 처리하자.

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1