[백준] 5972 택배 배송 (복습) + 다익스트라 알고리즘 정리
문제
농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.
농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.
다음 지도를 참고하세요.
[2]---
/ | \
/1 | \ 6
/ | \
[1] 0| --[3]
\ | / \2
4\ | /4 [6]
\ | / /1
[4]-----[5]
3 농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.
농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.
입력
첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.
둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.
출력
첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.
각 정점과 정점과 정점을 잇는 비용이 주어져있고, 1번부터 N번 정점까지 이동할때 가장 적은 비용을 출력하는 문제입니다.
다익스트라 알고리즘을 이용합니다.
입력은 인접리스트에 저장합니다.
우선순위 큐를 이용한 두가지 방법입니다.
#include <bits/stdc++.h>
using namespace std;
int n, m, dist[50001];
vector<pair<int, int>>adj[50001];
int dij() {
memset(dist + 1, 0x3f, sizeof(dist));
priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int,int>>>pq; //최소힙을 사용했습니다.
pq.push({ dist[1] = 0,1 });
while (!pq.empty()) {
auto [cdist, cur] = pq.top();
pq.pop();
if (dist[cur] < cdist)continue; // *별표 만약 이미 갱신된 값보다 멀면 continue
for (auto [to, cost] : adj[cur]) { //갱신 후보
if (dist[to] > cdist + cost) {
pq.push({ dist[to] = cdist + cost,to });
}
}
}
return dist[n];
}
int dij2() {
memset(dist+1, 0x3f, sizeof(dist));
priority_queue<pair<int, int>, vector<pair<int, int>>> pq; //최대힙을 사용했습니다.
dist[1] = 0;
pq.push({ 0,1 });
while (!pq.empty()) {
auto top = pq.top(); pq.pop();
int cur = top.second;
for (auto [nxt, cost] : adj[cur]) {
if (dist[nxt] > dist[cur] + cost) {
dist[nxt] = dist[cur] + cost;
pq.push({ -dist[nxt],nxt }); //최대힙을 사용한 대신, 정렬하기위해 거리*-1을 해줍니다.
}
}
}
return dist[n];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
int a, b, c;
while (m--) {
cin >> a >> b >> c;
adj[a].push_back({ b,c });
adj[b].push_back({ a,c });
}
cout << dij();
}다익스트라 알고리즘은 매번 현재 위치를 기준으로 다른 정점으로 다다르는 거리가 짧아지면 그 정점을 갱신합니다.
현재 위치를 기준으로 한다는 점은 현재 위치의 갱신된 거리는 반드시 최소라는 근거가 있기 때문입니다.
현재 위치가 최소라는 근거는, 만약 현재 위치에 오기위해 다른 점을 거친다면 그 거리가 무조건 더 멀기 때문입니다.
따라서 이전에 다익스트라를 공부 했을때는, 현재 위치에 대해 방문처리 visited를 해주었습니다.
따라서 아래처럼 visited 배열을 이용해 방문처리를 해주어도 정답입니다.
int visited[50001];
int dij() {
memset(dist + 1, 0x3f, sizeof(dist));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; //최소힙을 사용했습니다.
pq.push({ dist[1] = 0,1 });
while (!pq.empty()) {
auto [cdist, cur] = pq.top();
pq.pop();
if (visited[cur])continue;
visited[cur] = 1;
for (auto [to, cost] : adj[cur]) { //갱신 후보
if (dist[to] > cdist + cost) {
pq.push({ dist[to] = cdist + cost,to });
}
}
}
return dist[n];
}하지만 위의 dij , dij2 함수에는 방문처리가 없습니다.
손으로 쓰면서 왜 방문처리가 필요하지 않은지 살펴보았습니다.
cur:1 일때 , pq에는 {4,4}가 push 되어있습니다. 4번 정점으로 가기위해 거리가 4로 갱신되었다는 의미입니다.
하지만 이후 cur:2 일때, pq에 {1,4}가 push 되었습니다. pq안에는 {4,4}도 들어있습니다.
이때, cur:4로 현재위치가 4 즉 4번 정점의 거리는 최소거리로 확정 되어있으므로, 또다시 {4,4}로 갱신될 일은 없습니다.
만약 거리의 최솟값을 top으로 올리는 우선순위 큐가 아니라 그냥 큐였다면 어떻게 될까 생각을 해봤습니다. 그렇게되면
cur:2일때, {1,4}가 아니라 {4,4}가 먼저 위로 올라오게 될 것입니다.
노드의 개수가 적은 간단한 예제에서는 정답을 찾을 수 있습니다. 하지만 제출을 눌러보면 시간초과가 뜨게 됩니다.
for (auto [to, cost] : adj[cur]) { //갱신 후보
if (dist[to] > cdist + cost) {
pq.push({ dist[to] = cdist + cost,to });
}
}
짧은 거리의 지점을 현재위치로 삼지 않기때문에, 큐에 너무 많은 값이 들어가고 나갈 수밖에 없습니다. 따라서 시간초과가 발생합니다.
따라서 다익스트라 알고리즘의 결론은 다음과 같습니다.
1.우선순위큐는 반드시 사용해야합니다.
갱신 후, 가장 거리가 짧은 지점을 현재위치로 지정후 다시 갱신을 반복하면, 큐에 들어가고 나오는 데이터를 최소화 할 수 있습니다.
2. 우선순위 큐를 사용하게되면 방문처리를 하지 않아도, 최소거리임을 보장받기 때문에 또다시 갱신될 일이 없습니다.