1. 문제 설명

엔터프라이즈호 탈출

2. 문제 분석

다익스트라를 통해 시작 위치("E")에서 다른 모든 노드에 대한 최단 거리를 구할 수 있다. 최단 거리 배열에서 가장자리 위치의 최솟값이 곧 탈출할 수 있는 가장 짧은 거리다. 처음에는 모든 가장자리 값을 비교한 뒤 최속값을 리턴했는데, 파이썬 언어에서는 시간 초과가 났다. 결국 다익스트라 알고리즘 로직 중 현재 위치가 가장자리이기만 하면 곧바로 값을 리턴(최솟값을 보장 가능)하는 형식으로 시간을 줄였다.

3. 나의 풀이

import sys
import heapq

INF = sys.maxsize
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    k, w, h = map(int, sys.stdin.readline().rstrip().split())
    class_dict = {}
    for _ in range(k):
        name, time = sys.stdin.readline().rstrip().split()
        time = int(time)
        class_dict[name] = time
    class_dict["E"] = 0
    start_row, start_col = 0, 0
    nodes = []
    for i in range(h):
        position = sys.stdin.readline().rstrip()
        for j in range(w):
            if position[j] == "E":
                start_row, start_col = i, j
        nodes.append(position)

    def Dijkstra(start_row, start_col):
        distances = [[INF for _ in range(w)] for _ in range(h)]
        distances[start_row][start_col] = 0
        pq = []
        heapq.heappush(pq, [0, start_row, start_col])

        while pq:
            cur_cost, cur_row, cur_col = heapq.heappop(pq)

            if cur_row == 0 or cur_row == h-1 or cur_col == 0 or cur_col == w-1: return cur_cost

            if distances[cur_row][cur_col] < cur_cost: continue

            for x, y in zip(dx, dy):
                next_row, next_col = cur_row + y, cur_col + x
                if next_row < 0 or next_col < 0 or next_row >= h or next_col >= w: continue

                next_cost = class_dict[nodes[next_row][next_col]]
                if distances[next_row][next_col] > cur_cost + next_cost:
                    distances[next_row][next_col] = cur_cost + next_cost
                    heapq.heappush(pq, [cur_cost + next_cost, next_row, next_col])

        return -1
    answer = Dijkstra(start_row, start_col)
    print(answer)