BOJ 1854 K번째 최단경로 찾기(C++)

K번째 최단경로 찾기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	855	282	139	27.745%

문제

봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.

입력

첫째 줄에 n, m, k가 주어진다. (1≤n≤1000, 0≤m≤2000000, 1≤k≤100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 숫자 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1≤a, b≤n. 1≤c≤1000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.

출력

n개의 줄을 출력한다. i번째 줄에 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다.

예제 입력 

5 10 2
1 2 2
1 3 7
1 4 5
1 5 6
2 4 2
2 3 4
3 4 6
3 5 8
5 2 4
5 4 1

예제 출력 

-1
10
7
5
14

힌트

출처

• 문제의 오타를 찾은 사람: Hibbah

알고리즘 분류

• K번째 최단 경로

#include    <cstdio>
#include    <vector>
#include    <queue>
#pragma warning(disable:4996)
 
std::vector< std::pair<int, int> > edges[1111]; //a -> b c시간 일 때 최대 2000000 * 1000의 시간이 나올 수 있음
std::priority_queue<int> paths[1111];
 
struct comp
{
    bool operator()(const std::pair<int, int> & a, const std::pair<int, int> & b) 
    {
        return a.second > b.second;
    }
};
std::priority_queue< std::pair<int, int>, std::vector<  std::pair<int, int> >, comp > q; //다익스트라 알고리즘용
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
 
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[a].push_back(std::make_pair(b, c));
    }
 
    //다익스트라 알고리즘 
    q.push(std::make_pair(1,0)); //1번 점으로 가는데 최단 경로는 0 (시작점이므로)
    paths[1].push(0);
    while (!q.empty())
    {
        int vertex = q.top().first;
        int time = q.top().second;
        q.pop();
 
        for (auto next : edges[vertex])
        {
            if (paths[next.first].size() < k)
                paths[next.first].push(time + next.second);
            else if (paths[next.first].top() > time + next.second)
            {
                paths[next.first].pop();
                paths[next.first].push(time + next.second);
            }
            else
                continue;
 
            q.push(std::make_pair(next.first, time + next.second));
        }
    }
 
    for (int i = 1; i <= n; ++i)
        printf("%d\n", (paths[i].size() == k) ? paths[i].top() : -1);
 
    return 0;
}

k번째 최단경로 찾기 문제. 

이 문제는 시작점 1부터 1-1, 1-2, .... 1-n까지 모든 정점에 대하여 k번째 최단경로를 찾는 문제이다. 

우선 k를 고려하지 않고 최단경로를 찾는 알고리즘은 여러가지가 있다. 

플로이드 알고리즘의 경우 시간복잡도가 n^3으로 시간초과가 날 것이 뻔하다. 

벨만포드 알고리즘도 있는데 이것은 음수가중치가 있을 경우 주로 사용한다. 최악의 경우를 보았을 때 다익스트라만한 알고리즘도 없다. 

때문에 여기서는 다익스트라 알고리즘을 사용하였다. 

다익스트라(dijkstra) 알고리즘은 시작 정점에서 갈 수 있는 정점에 대해 차례로 최단경로를 계산하는 greedy alghritm이다. 

여기서 k번째가 추가된다면 어떻게 해야 할까 고민하던 중 

max heap을 사용하면 어떨까 하는 생각이 들었다.

1. 각 정점은 모두 k개의 경로를 가질 수 있는 heap을 만든다. (paths 변수)

2. 가장 작은 가중치 부터 차례대로 모든 경로에 대해 계산하면서 만약 해당하는 정점의 heap에 

2-1. k개의 경로가 차지 않았을 경우 넣어준다. (41라인)

2-2. k개의 경로가 이미 존재할 경우 heap의 root 노드가 k번째 최단경로가 된다. 이 경로보다 작은 경우 기존의 k번째 경로를 제거하고 넣어준다.(43라인)

2-3. 해당 정점에 k개의 경로가 존재하며 이번에 계산한 경로가 기존의 경로보다 긴 경로일 경우에는 생각할 필요가 없다. 

이렇게 계산해 나간다면 모든 정점에 대해 최단경로만을 가지고 다음 정점의 경로를 계산하는 것이 아닌 

모든 정점에 대해 최대 k개의 경로를 가지고 다음 정점의 경로를 계산하므로 다양한 경로가 나올 것이다. 

순서대로 최단경로를 찾기 위해 min heap을 이용하였다.(q 변수) 

주의할 점은 

1. 31라인에 정점 1의 1번째 최단경로는 0이다. 이것을 안넣어주어서 계속 틀렸었다...

2. 최단경로는 최대 2000000개의 간선을 모두 사용한다고 해도 최대 가중치가 1000이므로 int범위 내에 들어온다. 하지만 더 많아진다면 long long int 등도 고려해야 할 것 같다.