[알고리즘] 최단거리

접근 방식

• 다익스트라를 이용해서, 최단 거리 계산후에 출력
  • 지금까지 방문해서, 추가 해놓은 노드들 중에 우선 순위가 높은(거리가 가까운) 노드(curr)를 선택한 후
  • 그 노드와 인접한 노드(next)의 거리를 판별한다 (min(next의 원래 거리, curr을 거쳤을때의 거리))
• 우선 순위가 가장 높은 노드를 찾을 때 for 문을 이용해서 하려고 했더니 시간 초과 발생
• 우선 순위가 가장 높은 노드를 찾을 때 우선순위 큐를 사용해서, PQNode 라는 클래스를 생성해서, dist 가 작을 수록 높은 우선 순위를 가지는 min 힙을 만들려고 했지만, 시간 초과 발생

class PQNode
{
public:
   PQNode() :idx(0) {}
   PQNode(int i, int d) :idx(i), dist(d){}
public:
   int idx;
   int dist;

   bool operator<(const PQNode n) const
   {
       return this->dist > n.dist;
   }
};

• 클래스를 따로 생성하지 않고, pair 를 이용해서 원소를 음수로 치환해서 사용하니, 통과 되었다.. 미리 구현된 자료형이랑 시간차이가 많이 나나..?

#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>

using namespace std;
class Vertex;
class Edge;
void solution(int N, vector<Vertex>& graph, int startIdx);
void dijkstra(int N, vector<Vertex>& graph, int startIdx);

class Edge
{
public:
    Edge() {}
    Edge(Vertex* v, int w) : toVertex(v), Weight(w) {}
public:
    Vertex* toVertex;
    int Weight;
};

class Vertex
{
public:
    Vertex() :idx(0){}
    Vertex(int value):idx(value) {}

public:
    int idx;
    vector<Edge> edges;
};


int main()
{
    int V, E, K;
    cin >> V >> E >> K;
    vector<Vertex> graph = vector<Vertex>(V +1);
    
    for (int i = 1; i <= V; i++) graph[i] = Vertex(i);
    for (int i = 1; i <= E; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from].edges.push_back(Edge(&graph[to], weight));
    }
    solution(V, graph, K);
}

int dist[300001] = {};

void solution(int N, vector<Vertex>& graph, int startIdx)
{
    fill_n(dist, size(dist), INT_MAX);
    dijkstra(N, graph, startIdx);
    for (int i = 1; i <= N; i++)
    {
        if (dist[i] == INT_MAX)
            cout << "INF" << "\n";
        else
            cout << dist[i] << "\n";
    }
}

void dijkstra(int N, vector<Vertex>& graph, int startIdx)
{
    priority_queue<pair<int,int>> pq;
    dist[startIdx] = 0;
    pq.push({ 0, startIdx });
    while (!pq.empty())
    {
        int currIdx = pq.top().second;
        int currDist = - pq.top().first;
        pq.pop();

        if (dist[currIdx] < currDist)
            continue;
        for (auto it = graph[currIdx].edges.begin(); it != graph[currIdx].edges.end(); it++)
        {
            int nextIdx = (*it).toVertex->idx;
            
            if (dist[nextIdx] > currDist + (*it).Weight)
            {
                dist[nextIdx] = currDist + (*it).Weight;
                pq.push({ -dist[nextIdx], nextIdx });
            }
 
        }
    }
}