1249. SW 문제해결 응용 4일차 - 보급로

태그 잊지 않고 붙이세요
#Algorithm #출제사이트 #D4 #Solved #Dijkstra
문제 링크

제한사항

가장 첫 줄은 전체 테스트케이스의 수이다.
각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.
그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

접근 방법

문제엔 복구 시간이라고 쓰였지만 간선과 가중치로 단순하게 생각해보자.
지도의 위치가 노드이며 복구 시간은 해당 노드로 이어진 간선의 가중치다.

점과 점 사이 최소 거리로 문제를 단순화할 수 있다. 다익스트라로 해결 가능하다.

복잡도

시간복잡도: (V + E) * logE (V는 노드의 개수, E는 간선의 개수)
공간복잡도: O(E)

코드

import heapq

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    size = int(input())
    war_map = [list(map(int, input())) for _ in range(size)]
    dists = [[10**9] * size for _ in range(size)]
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    start = (0, 0)

    my_deque = []
    heapq.heappush(my_deque, (0, (0,0)))
    dists[0][0] = 0

    while my_deque:
        dist, position = heapq.heappop(my_deque)
        for dir in directions:
            next_row = dir[0] + position[0]
            next_col = dir[1] + position[1]

            if next_row not in range(size) or next_col not in range(size):
                continue

            next_dist = dist + war_map[next_row][next_col]
            if next_dist < dists[next_row][next_col]:
                dists[next_row][next_col] = next_dist
                heapq.heappush(my_deque, (next_dist, (next_row, next_col)))

    print(f"#{test_case} {dists[size - 1][size - 1]}")