[다익스트라] 1249 보급로

NxN의 맵이 있다. (0, 0)에서 출발해서 (N-1, N-1)까지 이동을 하려고하는데 중간중간에 도로들이 파손이 되어있다. 파손된 도로를 복구하는데 걸리는 시간은 각 칸에 적힌 수만큼 걸린다. 도로를 이동할 때 걸리는 시간을 제외하고 출발지부터 도착지까지 복구하면서 이동할 때 걸리는 시간이 최소인 시간을 구하라.

---

접근

- 기본적으로 다익스트라를 적용시켰다.

- 2차원 맵이기 때문에 현재위치에서 상하좌우 칸에 대한 시간을 구하여 최솟값을 갱신해나간다.

 

구현

- 2차원 맵에 대한 정보를 입력받아 graph라는 2차원 리스트에 저장한다.

- 이후 solve함수에서 해를 구하여 반환한다.

- 다음은 solve함수에 대한 코드이다.

- 먼저 각 칸을 INF로 초기화하여 나중에 최솟값으로 갱신될 수 있도록 한다.

- 우선순위 큐를 활용하여 다른 칸을 탐색하고 (소요시간, Y, X) 순으로 저장한다.

    INF = 987654321
    dist = [[INF for _ in range(N)] for _ in range(N)]

    hq = []
    heapq.heappush(hq, (0, 0, 0))
    dist[0][0] = 0

 

- BFS 탐색을 한다.

- 현재 위치의 최솟값이 현재 꺼낸 값보다 작으면 더 이상 탐색하지않고 다음 위치를 탐색한다.

    while hq:
        cur_weight, cy, cx = heapq.heappop(hq)
        if dist[cy][cx] < cur_weight:
            continue

 

- 현재위치를 기준으로 상하좌우를 탐색한다.

- 다음 위치가 맵 범위 내에 있을 때 현재까지의 시간과 다음 칸의 시간을 더해서 weight에 저장한다.

- 다음위치에 저장되어있는 최솟값과 weight와 비교하여 weight가 더 작다면 최솟값을 갱신한다.

- 그리고 다음에 탐색할 수 있도록 힙에 저장한다.

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx):
                weight = graph[ny][nx] + cur_weight
                if dist[ny][nx] > weight:
                    dist[ny][nx] = weight
                    heapq.heappush(hq, (weight, ny, nx))

 

- 위에서 BFS 탐색이 종료되었을 때 (N-1, N-1)에 최종적인 해가 저장되어있을 것이고 이를 반환한다.

    return dist[N-1][N-1]

---

전체 코드

import sys
import heapq
sys.stdin = open("input.txt")

test_case = int(input())

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < N)

def solve():
    INF = 987654321
    dist = [[INF for _ in range(N)] for _ in range(N)]

    hq = []
    heapq.heappush(hq, (0, 0, 0))
    dist[0][0] = 0

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    while hq:
        cur_weight, cy, cx = heapq.heappop(hq)
        if dist[cy][cx] < cur_weight:
            continue

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx):
                weight = graph[ny][nx] + cur_weight
                if dist[ny][nx] > weight:
                    dist[ny][nx] = weight
                    heapq.heappush(hq, (weight, ny, nx))

    return dist[N-1][N-1]

for tc in range(test_case):
    N = int(input())
    graph = [list(map(int, input())) for _ in range(N)]

    answer = solve()
    print("#{} {}".format(tc+1, answer))