문제

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

입력 예시 1

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

출력 예시 1

4

문제 이해

기본적인 다익스트라 구현문제인줄 알았는데 통수를 맞은 문제다. 하지만 덕분에 많이 배워 간다.

일단 이 문제 다익스트라를 한번만 돌리면 풀 수 있다. 시간제한이 0.5초라서 시간복잡도를 한번 계산해봤다.

10만 log 1,000
= 10만 10
= 100만

1초에 1억번 정도 계산하니까 충분하다고 생각했고, 당당하게 코드를 제출했는데 시간초과가 났다. 시간복잡도를 따지면 충분한 시간인데 왜 시간초과가 났는지 의문이 생겼다.

이 질문을 보고 답을 알 수 있었다.
https://www.acmicpc.net/board/view/120269

이 문제가 중복되는 간선이 없으면 시간초과가 날리가 없다. 즉, 간선이 중복되지 않거나 각 노드쌍마다 유일한 경로만 있을 때는 충분한 시간인데, 같은 노드에 대해 여러 번 다른 비용으로 도달할 수 있다면 시간초과가 날 수도 있다. -> 이 문제 덕분에 이렇게도 시간초과가 날 수 있단걸 알았다.

이 문제를 해결하려면 코드 40-41번 처럼 조건문을 만들어줘야 한다.

if cost[cur_node] < cur_cost:
        continue

이 코드를 추가하면 이미 더 적은 값으로 처리되었을때 for 반복문을 무의미하게 돌리지 않고 사전에 막을 수 있다. 만약 이 코드가 없으면 이미 최소비용이 먼저 들어와서 처리를 했는데도 for문으로 비교를 해야했을거다. 그렇다고 값이 변하지는 않지만 그 시간이 시간초과를 낼만큼 클 수도 있나보다.

난 이 코드를 이해하기 위해서 chatGPT를 이용했다. 아래에는 내가 보고 도움이 되었던 설명이다.

chat GPT로 이해한 설명

답변 1
if cost[cur_node] < cur_cost: continue 이 구문을 쉽게 설명하자면, 이미 처리된 노드를 다시 처리하지 않도록 하는 조건입니다.

다익스트라 알고리즘에서 일어나는 일

다익스트라 알고리즘은 최단 경로를 찾는 알고리즘입니다. 각 노드에 대해 최소 비용을 기록하면서, 우선순위 큐를 이용해 가장 적은 비용으로 갈 수 있는 노드부터 차례로 탐색합니다.

그런데, 우선순위 큐에 같은 노드가 여러 번 들어갈 수 있습니다. 예를 들어, 어떤 노드가 처음에는 큰 비용으로 큐에 들어가고, 나중에 더 작은 비용으로 다시 들어갈 수 있습니다. 그러면 큐에서 꺼낸 값이 이미 더 작은 값으로 갱신된 값보다 더 큰 경우가 생깁니다.

if cost[cur_node] < cur_cost: continue 의 의미

1. cost[cur_node]는 해당 노드까지의 현재 최단 비용입니다.
2. cur_cost는 큐에서 꺼낸 현재 노드의 비용입니다.

즉, cost[cur_node]가 더 작으면 이미 더 작은 비용으로 그 노드를 처리한 적이 있다는 뜻입니다. 그러므로 이 노드는 다시 처리할 필요가 없고, 그냥 넘겨버려야 합니다. 이때 continue가 실행됩니다.

예시로 설명:

• 처음: 노드 A의 최단 비용이 10이라고 기록되어 있고, 큐에 10으로 들어갔습니다.
• 나중: 노드 A가 다시 큐에 들어가지만, 이번에는 15라는 비용이 들어갔습니다.

이 경우, 15는 이미 10보다 큰 값이므로 불필요한 작업입니다. 큐에서 꺼내서 다시 계산할 필요가 없으므로, continue를 사용하여 건너뛰는 것입니다.

결론

if cost[cur_node] < cur_cost: continue는 이미 더 작은 비용으로 처리된 노드를 다시 처리하지 않도록 하기 위한 조건입니다. 이 조건을 통해 불필요한 계산을 줄여 알고리즘을 더 빠르게 만들 수 있습니다.

---

질문 2.
이미 더 작은 값으로 처리된 노드가 의미없이 반복문을 돌지 않도록 방지(최적화)하는 건가?

답변 2.
네, 맞습니다! if cost[cur_node] < cur_cost: continue 구문은 이미 더 작은 값으로 처리된 노드가 반복문에서 의미 없이 다시 처리되는 것을 방지하는 최적화입니다.

왜 이 조건이 중요한가요?

다익스트라 알고리즘에서는 우선순위 큐(Priority Queue)를 사용해 가장 작은 비용을 가진 노드를 먼저 꺼내서 처리합니다. 하지만 큐에 넣는 과정에서 동일한 노드가 여러 번 들어갈 수 있습니다. 예를 들어, 어떤 노드에 대한 경로를 처음에는 비효율적인 방법으로 계산하고 큐에 넣었지만, 나중에 더 적은 비용으로 그 노드를 다시 큐에 넣을 수 있습니다.

이럴 때, 큐에서 꺼낸 노드가 이미 더 작은 비용으로 처리된 적이 있다면 다시 계산할 필요가 없습니다. 즉, 그런 노드는 반복적으로 계산하는 시간을 낭비할 뿐입니다.

이 구문은 바로 그런 불필요한 작업을 방지하는 역할을 합니다.

구문 설명

if cost[cur_node] < cur_cost:
    continue

• cost[cur_node]: 이 값은 현재까지 계산된 노드 cur_node의 최소 비용입니다.
• cur_cost: 우선순위 큐에서 꺼낸 현재 노드의 비용입니다.

이 조건이 의미하는 것은 현재 노드를 꺼냈을 때, 큐에 들어간 비용(cur_cost)이 이미 기록된 최소 비용(cost[cur_node])보다 크다면, 그 노드는 이미 더 작은 비용으로 처리된 상태이므로 다시 계산할 필요가 없다는 것입니다. 그래서 그 노드를 건너뛰게 하는 것입니다.

예시로 쉽게 풀어보겠습니다

예시 1:

• 최초: 노드 A의 최단 경로가 10으로 기록됩니다.
• 우선순위 큐에 10이 들어갑니다.
• 나중에: 노드 A가 다시 큐에 들어가는데, 이번에는 더 작은 비용인 8로 들어갑니다.

이때, 큐에서 꺼낸 8은 실제로 더 작은 비용이기 때문에 이 값을 처리해야 합니다. 그래서 cost[A]가 8로 갱신됩니다.

예시 2:

• 최초: 노드 B의 최단 경로가 20으로 기록됩니다.
• 우선순위 큐에 20이 들어갑니다.
• 나중에: 노드 B가 다시 큐에 들어가는데, 이번에는 25라는 비용으로 들어갑니다.

이때, cur_cost가 25이고 cost[B]가 20이므로 cur_cost가 더 크므로 이 노드는 이미 처리된 값이기 때문에 불필요한 연산을 피하기 위해 건너뛰게 됩니다.

최적화의 장점

이 조건을 넣음으로써, 불필요한 계산을 줄여 알고리즘의 성능을 높일 수 있습니다. 큐에서 꺼낸 노드가 이미 더 작은 비용으로 처리되었다면, 그 노드는 더 이상 처리할 필요가 없으므로 반복적인 계산을 피할 수 있습니다.

따라서, 전체 알고리즘의 시간 복잡도를 최적화하고, 성능을 더욱 향상시킬 수 있습니다.

---

질문 3
간선이 중복으로 여러개 사용될 수 있는 조건에서만 쓰면 되지않나? 두개의 노드쌍마다 오고 가는 것 2개밖에 없으면 이걸 적용안해도 되나?

답변 3
네, 정확히 이해하셨습니다. if cost[cur_node] < cur_cost: continue 구문은 간선이 중복될 수 있는 경우에 필요합니다. 간선이 중복되는 경우는 같은 노드에 대해 여러 번 다른 비용으로 도달할 수 있을 때가 해당됩니다. 반면, 간선이 중복되지 않거나 각 노드쌍마다 유일한 경로만 있을 때는 이 조건이 꼭 필요하지 않습니다.

간선 중복이 있을 때와 없을 때

1. 간선이 중복될 수 있는 경우

• 간선이 여러 번 중복될 수 있는 경우, 같은 노드에 대해 여러 번 다른 비용으로 도달할 수 있습니다.
• 예를 들어, 노드 A에서 노드 B로 가는 경로가 두 개 이상 있고, 그 경로마다 비용이 다를 수 있습니다.
• 이런 경우, 우선순위 큐에 같은 노드가 여러 번 들어갈 수 있으며, 큐에서 꺼낸 노드가 이미 더 작은 비용으로 처리된 노드일 수 있습니다. 이런 중복된 계산을 방지하기 위해 if cost[cur_node] < cur_cost: continue 조건이 필요합니다.

2. 간선이 중복되지 않는 경우

• 만약 각 노드쌍에 대해 단 하나의 경로만 존재하고, 각 경로의 비용이 고정되어 있다면, 중복된 비용으로 큐에 들어가는 일이 없습니다.
• 즉, 한 번 처리된 노드에 대해서는 더 이상 큐에 다시 들어갈 일이 없기 때문에, 이 조건 없이도 정상적으로 동작합니다.

예시로 비교

1. 간선이 중복되는 경우

1 → 2 (비용 10)
2 → 3 (비용 10)
1 → 3 (비용 20)

이때, 1 → 2 → 3 경로가 비용 20으로 연결되지만, 1 → 3 직접 연결되는 경로가 비용 20입니다. 큐에서 꺼낸 후, 다시 같은 노드를 처리해야 할 수도 있기 때문에, 중복된 계산을 피하기 위해 if cost[cur_node] < cur_cost: continue 조건이 필요합니다.

2. 간선이 중복되지 않는 경우

1 → 2 (비용 10)
2 → 3 (비용 10)

이 경우, 1 → 2 → 3 경로만 존재하므로, 큐에서 2번만 처리하고 더 이상 같은 노드가 큐에 들어가지 않기 때문에 if cost[cur_node] < cur_cost: continue 조건 없이도 잘 동작합니다.

결론

• 간선이 중복될 수 있는 경우 (즉, 동일한 노드쌍에 대해 여러 개의 경로가 있을 경우), 이 조건이 필요합니다. 왜냐하면, 여러 번 큐에 들어갈 수 있는 노드를 효율적으로 처리하기 위해서입니다.
• 간선이 중복되지 않는 경우 (각 노드쌍에 대해 유일한 경로만 있을 경우), 이 조건 없이도 문제없이 동작합니다. 이 경우, 같은 노드는 한 번만 큐에 들어가므로, continue를 사용할 필요가 없습니다.

따라서, 두 노드쌍 간에 한 개의 경로만 존재한다면, 이 최적화 조건은 필요하지 않습니다.

코드

# 백준 1916번 최소비용 구하기

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

# Import PriorityQueue
from queue import PriorityQueue

# 0. 입력 및 초기화
INF = int(1e12)
N = int(input())
M = int(input())

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

start_node, end_node = map(int, input().split())

# 시작점과 도착점이 같은 경우 처리리
if start_node == end_node:
    print(0)
    sys.exit(0)

# 2. Excute Dijkstra Algorithm
cost = [INF] * (N+1)

pq = PriorityQueue()
pq.put([0, start_node]) # cur_cost, cur_node
cost[start_node] = 0

while not pq.empty():

    cur_cost, cur_node = pq.get()

    # 이미 더 작은 값으로 처리된 노드가 의미없이 반복문을 돌지 않도록 방지(최적화화)
    if cost[cur_node] < cur_cost:
        continue
    # 이 조건은 같은 경로에 간선이 여러개 있을때 유효함.
    # 간선이 중복되지 않거나 각 노드쌍마다 유일한 경로만 있을 때는 필요 없음.

    for adj_node, adj_cost in adj_list[cur_node]:

        temp_cost = cur_cost + adj_cost

        if temp_cost < cost[adj_node]:
            cost[adj_node] = temp_cost
            pq.put([temp_cost, adj_node])

# 3. Print result
print(cost[end_node])

이 문제는 40-41번 코드가 없으면 시간초과가 난다. 이 문제만이 아니라 같은 경로에 두 개 이상의 경로가 있는 다익스트라 상황이면 이렇게 처리해야 한다.