부끄럽지만 수도없이 많은 도전 끝에 맞춘 문제이다. 정확한 개념을 잡는게 중요하다는 것을 깨닫게 해주었던 문제…

문제

  • 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

  • 첫째 줄에 정점의 개수 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를 출력하면 된다.

예제

예제 입력
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력
0
2
3
7
INF

접근

  • 하나의 정점에서 다른 정점까지의 최단 경로를 구하는 방법중 가장 대표적인 방법은 다익스트라 알고리즘이다!

내가 생각한 풀이

  • 다른 블로그를 참조하여 다익스트라 알고리즘의 순서를 익혔고 그것을 토대로 나의 코드로 옮겼다.
  • 다익스트라 알고리즘은 우선순위 큐 즉 힙을 이용하여 푸는 것이 효율적이다.
  • 출발하는 정점의 정보를 힙에 넣은 후 그 주변 노드를 탐색한다. 이 때 기존 dist 배열의 값이 현재 정점까지의 거리 + 노드의 가중치보다 작으면 정보를 힙에 추가시킨다.

문제를 풀면서 힘들었던 점

  • 처음에 계속해서 노드에 대한 힙을 만들어서 풀려고 했었다. 하지만 다익스트라의 힙에는 노드의 가중치가 아닌 현재까지의 거리가 들어와야 한다는 것을 인지하지 못했다. 알고리즘에 대한 정확한 이해가 얼마나 중요한지 깨달을 수 있었다.(무려 30번을 넘게 도전한 것 같다.)

코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define INF 1000000000
struct node{
  int end;
  int value;
};
struct vertex{
  int idx;
  int d;
  int p;
};
struct cmp{
  bool operator()(vertex a, vertex b){
      return a.d>b.d;
  }
};
int main(void){
  cin.tie(NULL); cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  priority_queue<vertex, vector<vertex>, cmp> pq;
  vector<struct node> n[20001];
  int V,E,S,dist[20001];
  cin>>V>>E>>S;
  for(int i = 0 ;i<E;i++){
    int t1,t2,t3;
    cin>>t1>>t2>>t3;
    n[t1].push_back({t2,t3});
  }
  for(int i = 1 ;i<=V;i++){
    dist[i] = INF;
  }
  dist[S] = 0;
  pq.push({S,0,0});
  while(!pq.empty()){
    struct vertex temp = pq.top();
    pq.pop();
    for(int i = 0;i<n[temp.idx].size();i++){
      if(dist[n[temp.idx][i].end]>n[temp.idx][i].value + temp.d){
        dist[n[temp.idx][i].end] = n[temp.idx][i].value + temp.d;
        pq.push({n[temp.idx][i].end,dist[n[temp.idx][i].end],temp.idx});
      }
    }
  }
  for(int i = 1; i<=V;i++){
    if(dist[i]==INF) cout<<"INF"<<endl;
    else cout<<dist[i]<<endl;
  }
  return 0;
}