[ 백준 1753 ] 최단경로 (C++)

백준의 최단경로(1753) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 한 정점에서 다른 모든 정점까지 가는데 걸리는 최단 경로의 경로값, 즉, 최소비용을 구하면 되는 문제이다.

   하나의 정점에서 다른 모든 정점까지는데 걸리는 최소비용을 구하는 대표적인 알고리즘으로는

   다익스트라 알고리즘과 벨만포드 알고리즘이 있는데, 이 문제에서는 음의 가중치가 없기 때문에 다익스트라 알고리즘으로

   해결할 수가 있다.

   다익스트라 알고리즘을 잘 모른다면 아래의 글을 읽고 오도록 하자.

   [ 다익스트라 알고리즘 알아보기(Click) ]

 

2) 다익스트라에 대해서 이해했다면, 이 문제는 쉽게 해결할 수 있을 것이다.

   위의 링크로 걸어져있는 다익스트라를 설명하는 글에서 말했듯이, 배열만으로 구하는 방법과, 우선순위큐를 이용하는

   방법이 있는데, 이 문제를 본인이 2가지 방법으로 모두 구현해봤는데, 배열만으로 구하는 방법으로 제출할 시 메모리 초과가

   발생하게 된다. 아마, 정점의 갯수가 20,000개다 보니까 20,000 x 20,000 x 4 byte짜리 int형 배열을 만들어서 관리하다

   보니 메모리 초과가 발생하는 것 같다.

   그래서 우선순위큐를 이용한 코드로 패스를 받았다.

   아래 소스코드에는 그래도 2가지 코드 모두 올려놓겠다.

[ 우선순위큐를 이용한 소스코드(PASS) ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 20010
#define INF 987654321
using namespace std;
 
int V, E, Start;
int Dist[MAX];
vector<pair<int, int>> Vertex[MAX];
 
void Input()
{
    cin >> V >> E >> Start;
    for (int i = 0; i < E; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Vertex[a].push_back(make_pair(b, c));
    }
    for (int i = 1; i <= V; i++) Dist[i] = INF;
}
 
void Solution()
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, Start));
    Dist[Start] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < Vertex[Cur].size(); i++)
        {
            int Next = Vertex[Cur][i].first;
            int nCost = Vertex[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
 
    for (int i = 1; i <= V; i++)
    {
        if (Dist[i] == INF) cout << "INF" << endl;
        else cout << Dist[i] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 배열을 이용한 소스코드 (메모리초과) ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 20010
#define INF 987654321
using namespace std;
 
int V, E, Start; 
int MAP[MAX][MAX];
int Dist[MAX];
bool Select[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> V >> E >> Start;
 
    for (int i = 1; i <= V; i++)
    {
        Dist[i] = INF;
        for (int j = 1; j <= V; j++)
        {
            if (i == j) MAP[i][j] = 0;
            else MAP[i][j] = INF;
        }
    }
 
    for (int i = 0; i < E; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        MAP[a][b] = c;
    }
}
 
int Find_Shortest_Node()
{
    int Min_Dist, Min_Idx;
    Min_Dist = INF;
    Min_Idx = -1;
 
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == true) continue;
        if (Dist[i] < Min_Dist)
        {
            Min_Dist = Dist[i];
            Min_Idx = i;
        }
    }
    return Min_Idx;
}
 
void Update_Dist(int NewNode)
{
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == true) continue;
        if (Dist[i] > Dist[NewNode] + MAP[NewNode][i])
        {
            Dist[i] = Dist[NewNode] + MAP[NewNode][i];
        }
    }
}
 
void Dijkstra()
{
    for (int i = 1; i <= V; i++) Dist[i] = MAP[Start][i];
    Dist[Start] = 0;
    Select[Start] = true;
    
    for (int i = 0; i < V - 1; i++)
    {
        int NewNode = Find_Shortest_Node();
 
        Select[NewNode] = true;
        Update_Dist(NewNode);
    }
}
 
void Solution()
{
    Dijkstra();
    for (int i = 1; i <= V; i++)
    {
        if (Dist[i] == INF) cout << "INF" << endl;
        else cout << Dist[i] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
    
    return 0;
}