개요
-
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. -
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
접근방식
-
다익스트라 알고리즘에 관련한 문제를 익혀보기 위해서
남들의 풀이를 좀 보고 공부하려고 처음부터 검색했다. -
간선의 방향과 가중치를 저장하기 위해 선언한 adj벡터,
//index는 출발노드, value.first는 도착노드, value.second는 간선의가중치 vector<pair<int, int>> adj[Max_V];시작점으로부터 노드까지 최단거리기록용인 dist 배열
//시작점에서 index까지의 최단거리 int dist[Max_V];노드를 방문 하였는지 여부 기록용인 visited 배열
//index노드를 방문했는지 여부 bool visited[Max_V];시작점으로부터 노드까지 거리, 노드의 인덱스를 저장하는 우선순위 큐 pq
// {dist[node],node} 노드를 저장해서 dist값이 제일 작은값부터 반환 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;이렇게 컨테이너를 많이 사용하였다.
-
dist배열을 실행 중에 나올수없는 최대 수로 초기화를 하고,
방문배열도 false로 초기화를 해준다.fill(dist, dist + Max_V, INF); fill(visited, visited + Max_V, false); -
우선순위큐에 시작노드의 거리인 0과 시작노드를 넣어주고,
dist[시작노드]도 0으로 설정한다.//시작노드의 거리값 0으로 설정 dist[startNode] = 0; //우선순위큐에 시작노드에 해당하는 값 넣어줌 pq.push({ 0,startNode }); -
방문한적이 없는 pq의 top노드가 나올때까지,
pq.pop()하고 새로운 노드를 반복해서 뽑는다.
뽑는 도중에 pq가 비었다면 탈출해, 현재 뽑은 top노드가 방문한 적 있는지 체크한다.while (!pq.empty()) { //방문안한 노드이면서 dist가 제일 작은 값부터 주위노드로 뻗어나가기를 반복함 int curNode = pq.top().second; pq.pop(); while (!pq.empty() && visited[curNode]) { curNode = pq.top().second; pq.pop(); } //visited[curNode]==false일때가 아니라 pq가 empty일때 탈출한 상황이라면 체크해서 탈출 if (visited[curNode]) break; -
방문한적 없는 노드를 pq에서 뽑았다면 방문처리해주고,
해당 노드와 연결된 모든 노드를 for문을 이용해 탐색한다.
- 현재 노드를 거쳐서 연결된 노드로 이동하는 거리가
dist[연결된 노드] 보다 짧다면 갱신해주고,
pq에 연결된 노드를 넣어준다.//curNode에서 연결된 노드로 이동하는 거리 갱신 for (auto& p : adj[curNode]) { //cur노드를 거쳐서 p노드로 이동하는 거리가 dist[p.first]보다 짧다면 if (dist[p.first] > p.second + dist[curNode]) { //dist[p.first]값을 갱신해준다. dist[p.first] = p.second + dist[curNode]; //갱신될때마다 우선순위큐에 푸시해도 상관없다. 어차피 방문여부체크해서 제일 적은 값일때만 값을 체크해본다. pq.push({dist[p.first],p.first }); } }
전체코드
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int V, E, startNode;
const int Max_V = 20'000;
const int INF = 1'000'000'000;
//index는 출발노드, value.first는 도착노드, value.second는 간선의가중치
vector<pair<int, int>> adj[Max_V];
//시작점에서 index까지의 최단거리
int dist[Max_V];
//index노드를 방문했는지 여부
bool visited[Max_V];
// {dist[node],node} 노드를 저장해서 dist값이 제일 작은값부터 반환
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
//다익스트라 알고리즘
void Solution() {
while (!pq.empty()) {
//방문안한 노드이면서 dist가 제일 작은 값부터 주위노드로 뻗어나가기를 반복함
int curNode = pq.top().second;
pq.pop();
while (!pq.empty() && visited[curNode]) {
curNode = pq.top().second;
pq.pop();
}
//visited[curNode]==false일때가 아니라 pq가 empty일때 탈출한 상황이라면 체크해서 탈출
if (visited[curNode]) break;
//방문처리함.
visited[curNode] = true;
//curNode에서 연결된 노드로 이동하는 거리 갱신
for (auto& p : adj[curNode]) {
//cur노드를 거쳐서 p노드로 이동하는 거리가 dist[p.first]보다 짧다면
if (dist[p.first] > p.second + dist[curNode]) {
//dist[p.first]값을 갱신해준다.
dist[p.first] = p.second + dist[curNode];
//갱신될때마다 우선순위큐에 푸시해도 상관없다. 어차피 방문여부체크해서 제일 적은 값일때만 값을 체크해본다.
pq.push({dist[p.first],p.first });
}
}
}
for (int i = 0; i < V; i++) {
if (dist[i] == INF) cout << "INF" << '\n';
else cout << dist[i]<<'\n';
}
}
void Input()
{
fill(dist, dist + Max_V, INF);
fill(visited, visited + Max_V, false);
cin >> V >> E >> startNode;
startNode--;
//시작노드의 거리값 0으로 설정
dist[startNode] = 0;
//우선순위큐에 시작노드에 해당하는 값 넣어줌
pq.push({ 0,startNode });
for (int i = 0; i < E; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u - 1].push_back(make_pair(v - 1, w));
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
Solution();
}문풀후생
우선순위 큐를 이용해 제일짧은 거리를 가진 노드부터 시작하는 특성상
어떤 노드든 해당 노드로 가는 거리중 제일 짧은 값을 계속 비교하고 갱신하며 진행되어서 신기했다.
