[Algorithm]Baekjoon 1753번 :: 최단거리(다익스트라 알고리즘)

https://www.acmicpc.net/problem/1753

1753번: 최단경로

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
 
using namespace std;
 
 
struct Vertex
{
    int node;
    int distance; // distMap[node]값.
 
    Vertex(int _node, int _weight) : node(_node), distance(_weight) {};
};
 
struct cmp // 거리값 낮은것부터 뽑기.
{
    bool operator()(Vertex& a, Vertex& b)
    {
        return a.distance > b.distance;
    }
};
 
int distMap[20001] = { 0 };
vector<vector<Vertex>> graph;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    fill_n(distMap, 20001, 999999999); // 999999999으로 초기화.
    graph.resize(20001);
    
    int vertexCount = 0;
    int edgeCount = 0;
    int startVertexNum = 0;
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
    cin >> vertexCount >> edgeCount;
    cin >> startVertexNum;
 
    int start = 0;
    int dest = 0;
    int weight = 0;
    int lastNode = 0;
 
    for (int i = 0; i < edgeCount; i++)
    {
        cin >> start >> dest >> weight;
        graph[start].push_back(Vertex(dest, weight));
    }
 
    distMap[startVertexNum] = 0; // 시작노드거리값은 0.
    priority_queue<Vertex, vector<Vertex>, cmp> pq;
    Vertex startNode(startVertexNum, 0);
    pq.push(startNode);
    
    while (!pq.empty())
    {
        Vertex popedVertex = pq.top();
        pq.pop();
 
        int curNode = popedVertex.node;
        int curDist = popedVertex.distance;
 
        if (curDist > distMap[curNode]) continue; // 방문여부 확인.
 
        for (int i = 0; i < graph[curNode].size(); i++)
        {
            int next = graph[curNode][i].node;
            int nextDist = graph[curNode][i].distance;
 
            if (distMap[next] > curDist + nextDist)
            {
                distMap[next] = curDist + nextDist;
                pq.push(Vertex(next,distMap[next])); // 새로 갱신한것만 pq에 푸쉬..
            }
        }
    }
 
    for (int i = 1; i <= vertexCount; i++)
    {
        if (distMap[i] == 999999999)
        {
            cout << "INF" << '\n';
        }
        else
        {
            cout << distMap[i] << '\n';
        }
    }
}
 
 

다익스트라문제중 기본예제에 속하는 문제이다.

보통 프로그래머스가 편해서 자주 이용하지만, 각 알고리즘유형마다의 문제가짓수가 백준이 압도적으로 많기때문에 백준도 이용하게 된다.

 

기본원리는 시작노드를 설정하고, 방문하지 않은 노드중 최단거리의 노드를 선택 후, 최단거리맵을 갱신한다.

개인적인 생각으론 이런 알고리즘을 이해하는데는 예시그림을 보는게 최고다. 구글링을 적극 활용하자.

이 링크의 정리글이 보기 편한것 같다. https://freedeveloper.tistory.com/384

그리고 백준이든 프로그래머스든, 이런 알고리즘 문제 풀 때 예시로 주는 테스트케이스를 좀 더 다양한 유형의 케이스를 줬으면 좋겠다. 틀린코드인데도 예시 테스트케이스는 통과하는 경우가 있어서, 오히려 더 헷갈린다. 

 

다익스트라 알고리즘에서 각 노드에 '방문' 했다는 것은, 이후에 해당 노드에 대해 거리맵의 거리값을 갱신할 일이 없다는 것이다. 위 코드에 보면, 중간에 if (curDist > distMap[curNode]) continue; // 방문여부 확인.

라는 코드가 있다. 이 코드가 없어도 문제는 PASS가 뜬다. 수행속도를 비교하자면 해당코드의 유무차이는 4ms의 차이가 난다. 왜냐하면 방문여부를 확인 안하더라도,즉 이미 방문한 노드에 대해 검사를 또 하더라도 거리맵에는 비교를 통해 최소값만 기록하기 때문에 거리맵의 값들에 변동사항은 없다.

다만, 방문여부를 확인함으로써 불필요한 검사를 줄이기 때문에 수행속도가 좀 더 빨라진다.

이미 방문한 노드는 최단거리로 갱신된게 보장받기 때문에, 굳이 검사를 할 필요가 없는것이다.

고작 4ms의 차이라서 크게 신경쓸 필요가 없을수도 있다. 하지만 그렇게 생각하는 사람들을 위해 아래 링크를 준비했다.

https://www.acmicpc.net/board/view/34516

글 읽기 - ★☆★☆★ [필독] 최단경로 (다익스트라 알고리즘) FAQ ★☆★☆★

 

물론 위 링크에서 말했다시피 알고리즘 대회정도의 수준?에서나 집요하게 저격할 것 같고, 이번 1753번 문제같이 일반적인 문제에서는 그렇게까지 디테일하게 저격하지는 않는 것 같다. 실제로 방문여부코드가 없어도 통과되니까.

하지만 해당링크 글을 한번쯤 읽는것도 좋을것같다. 아직도 알아야 할 게 얼마나 많은지 체감시켜주는 글이다.