문제

문제 이해

다익스트라 문제를 풀고 있는데 다익스트라는 골드 범위 내의 문제 중에서는 활용이 잘 없는 것 같다. 애초에 다익스트라 문제를 사람들이 많이 안 풀었다. 만명도 안되는 다익스트라 문제가 수두룩하다. 왜 그런지는 잘 모르겠다.

• 방금 플레티넘 난이도인 1162번을 풀려고 했는데 dp에 대한 개념이 필요한 것 같다. 아직 질릴만큼 다익스트라 문제를 푼건 아니지만 슬슬 다른 알고리즘 개념으로 넘어갈 때가 된 것 같다.

이번 문제도 별 다를 게 없다. N-1번째를 제외하고 시야에서 안보이는 노드로는 지나가지 않으면서 0번에서 N-1번에 도달하는 최단거리를 구하면 된다. 시야에 있는 값은 간선을 아예 안 만들어주거나, 다익스트라를 돌릴때 우선순위 큐에서 값을 뺄때 걸러주거나 하면 풀 수 있다. 난 후자의 방법으로 해결했다.

코드

# 백준 17396번 백도어

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# Import PriorityQueue
from queue import PriorityQueue

# Function Dijkstra
def Dijkstra(cur_time, start_node):
    
    time = [INF] * N

    pq = PriorityQueue()
    pq.put([cur_time, start_node]) # cur_time이 앞인 이유는 첫번째 값을 기준으로 우선순위 큐가 값을 꺼낸다
    time[start_node] = 0

    while not pq.empty():

        cur_time, cur_node = pq.get()

        if sight[cur_node]: # 시야가 1이면 그냥 넘겨준다
            continue
        
        # 문제 특성상 노드에서 다른 노드까지 한 경로에는 길이 하나라 없어도 되지만, 다익스트라를 구현할 때 그냥 추가하면 좋음
        if cur_time > time[cur_node]: # 어차피 갱신되지 않을 값도 넘겨준다
            continue

        for adj_node, adj_time in adj_list[cur_node]:
            temp_time = cur_time + adj_time
            if temp_time < time[adj_node]:
                time[adj_node] = temp_time
                pq.put([temp_time, adj_node])
    return time

# 0. Input & Initialization
N, M = map(int, input().split()) # N노드 M간선
INF = int(1e12)

sight = list(map(int, input().split()))

# 1. Create adj_list
adj_list = [[] for _ in range(N)]
for _ in range(M):
    a, b, t = map(int, input().split())
    adj_list[a].append([b, t])
    adj_list[b].append([a, t])

# 2. Excute Dijkstra Algorithm
time_list = Dijkstra(0, 0) # cur_time, start_node

# 3. Print result
print(time_list[N-1] if time_list[N-1] != INF else -1)