다익스트라
다익스트라는 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 단일 시작점 알고리즘에 속하여 시작점을 기준으로 각 노드까지의 최단 거리를 알 수 있다. 이때 시간 복잡도를 줄이기 위해 우선순위 큐를 활용하면 좋다.
- 음수 간선이 없을때 사용 (음수가 있으면 벨만-포드나 플로이드를 사용하는게 좋다)
- 우선순위 큐를 활용
- 단일 시작점 알고리즘
다익스트라 알고리즘은 BFS처럼 동작한다. 시작점에서부터 BFS탐색을 진행한다. 단, 우선순위 큐에서 노드를 뽑을때는 간선의 가중치가 가장 낮은 노드를 뽑는다.(우선순위 큐에 {-가중치,노드} 형태로 넣으면 된다.) 해당 노드와 접한 노드를 뽑아서 dp에 최단경로를 메모이제이션한다. 이후 최단경로 가중치를 노드와 함께 큐에 넣고 루프를 돌며 반복한다.
문제 풀이
우선 의식의 흐름대로 문제를 읽으면 단순히 최단 경로를 구하는 프로그램을 작성하면 된다. 정점의 개수는 그럭저럭 크지 않아 보인다. 그러나 간선의 개수가 상당히 크다. 따라서 단순히 dp를 이차원배열로 만들어 구하면 메모리 초과가 날 가능성이 있다고 판단이 된다. 또한 w인 간선의 가중치는 10이하의 자연수 이므로 음수 가중치가 나오지 않는다. 따라서 벨만-포드나 플로이드 워샬을 사용하지 않아도 된다. 따라서 가장 적합한 다익스트라를 사용하면 되겠다는 판단이 들었다.
다익스트라 알고리즘을 사용하기 위해서는 우선순위 큐가 필요하다. 우선순위 큐에서는 루트값이 최댓값이다. 따라서 우선순위 큐를 사용할때 음수로 변환하여 사용하거나 비교 연산자를 만들어서 넣어야한다. 나는 연습삼아 만들어 보았다.(트루가 나오면 값의 위치가 교환된다. 즉 a가 더 크면 교환한다는 의미는 결국 앞에 최솟값이 온다는 소리이다.) 실제 코드에서는 귀찮으니 음수로 값을 넣어주고 뽑을때 양수로 뽑아주어 최소힙으로 사용했다.
struct cmp {
bool operator()(pair<int,int> a, pair<int,int> b) {
if (a.first > b.first)
return true;
else
return false;
}
};
cmp구조체를 우선순위 큐를 선언할때 넣어주어 최솟값을 루트값으로 두는 우선순위 큐를 만든다.
이후에 다익스트라 알고리즘은 기본형태와 비슷해서 크게 어려울것은 없다.
// 시작 점이 고정되어 있음.
// 음수 가중치 없음.
// 고로 다익스트라 사용하기 딱이다.
#include<iostream>
#include<vector>
#include<queue>
#define INF 987654321
using namespace std;
int V, E;
int startNode;
int dp[20001];
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> Vertex[20001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> V >> E;
cin >> startNode;
int u, v, w; // u에서 v로 가는 w 가중치, 즉 단방향 그래프
for (int i = 0; i < E; i++)
{
cin >> u >> v >> w;
Vertex[u].push_back({ v,w });
}
for (int i = 1; i <= V; i++) dp[i] = INF;
pq.push({ 0,startNode });//노드를 하나 넣어준다.
dp[startNode] = 0;
while (!pq.empty())
{
pair<int,int> tmp = pq.top();//가장 cost가 작은 것을 가져온다.
int cost = -tmp.first;
int start = tmp.second;
pq.pop();
if (dp[start] < cost)//갱신할 값보다 코스트가 크면 버린다.
continue;
for (int i = 0; i < Vertex[start].size(); i++)
{
int end = Vertex[start][i].first;
int endcost = Vertex[start][i].second;
// pq에 삽입한다.
if (dp[end] > cost + endcost) {
dp[end] = cost + endcost;
pq.push({-dp[end],end });
}
}
}
for (int i = 1; i <= V; i++)
{
if (dp[i] == INF)
cout << "INF" << '\n';
else
cout << dp[i] << '\n';
}
}
코드상에서 포인트라고 여겼던 것은 갱신할 값이 비교할 코스트보다 높은 경우 이후 연산을 생략하는 것이다. 우리는 최단경로를 구하고 있기 때문에 dp로 메모이제이션된 값이 더 작을 경우 코스트 연산이 불필요하다.(왜냐하면 음수 간선이 존재하지 않기 때문이다.) 따라서 이러한 경우를 생략해주면 된다.
결론 : 이번 경험을 통해 다익스트라의 기본 구조를 알 수 있었다. 또한 언제 다익스트라를 사용해야하는지 대략적으로 알 수 있었다.
'알고리즘' 카테고리의 다른 글
[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 ) (0) | 2021.08.06 |
---|---|
[python3] 백준 10844 풀이 ( 쉬운 계단 수, 다이나믹 프로그래밍, 이차 배열) (0) | 2021.08.05 |
[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드) (0) | 2021.08.02 |
[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드) (0) | 2021.07.26 |
[python3] 백준 1967 풀이 (트리의 지름, DFS) (0) | 2021.07.26 |