K번째 최단경로 찾기

 

k번째 최단경로를 찾는 문제이다.

1번 도시에서 i번 도시로 가는 k번째 최단경로 거리를 모두 출력해야 되기 때문에 다익스트라 알고리즘을 써야 한다.

k번째 최단경로를 찾아야 하기 때문에 기존의 다익스트라처럼 visit 배열을 체크해서 다시 오지 않는 방식이 아니라

어디에 방문을 하면, 그 노드의 우선순위큐에 거리를 넣는 방식을 쓴다.

 

우선순위큐를 노드의 개수 N개만큼 만들고, i번 도시에 방문을 하면, i번째 우선순위큐에 방문까지 걸린 거리를 push한다.

이때 큐의 크기가 K를 넘어가면 안되기 때문에 큐의 크기가 K보다 작을때는 그냥 push를 하고,

큐의 크기가 K일때는 top의 값과 비교를 해서 top보다 작으면 push를 한다.

top보다 크면 모든 경로를 정렬했다고 쳤을 때 어차피 K+1번째 이상에 위치하기 때문이다.

int next = road[t.num][i].num;
int dist = road[t.num][i].dist;
if(ans[next].size()<K)
{
    ans[next].push({t.dist+dist});
    pq.push({next,t.dist+dist});
}
else
{
    if(ans[next].top()>t.dist+dist)
    {
        ans[next].pop();
        ans[next].push(t.dist+dist);
        pq.push({next,t.dist+dist});
    }
}

핵심 코드이다.

처음에는 이 문제를 풀 때 visit을 체크하지 않으면 무한루프에 걸려서 어떻게 해결할지 꽤 고민했는데,

그냥 K번째 거리에 반영이 되면, 즉 큐의 크기가 K보다 작거나, 큐의 top값보다 현재 거리가 더 작을 때만 pq에 push를 해주면

해결된다.

이렇게 하면, 거리가 커지고 계속 돌다보면 결국 큐의 크기가 K보다 커지고, top값보다 현재 거리가 더 작아질 수 없기 때문에

push가 더 이상 안되고, 루프가 끝나게 된다.

 

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int N,M,K;
struct Data
{
    int num,dist;
    bool operator<(const Data r)const
    {
        return dist>r.dist;
    }
};
vector<Data>road[1004];
int kth[1004];
priority_queue<int> ans[1004];
priority_queue<Data> pq;
void Dijkstra()
{
    ans[1].push(0);
    pq.push({1,0});
    while(!pq.empty())
    {
        Data t = pq.top();
        pq.pop();
        if(ans[t.num].size()!=K) kth[t.num]=-1;
        else kth[t.num] = ans[t.num].top();
        for(int i=0;i<road[t.num].size();i++)
        {
            int next = road[t.num][i].num;
            int dist = road[t.num][i].dist;
            if(ans[next].size()<K)
            {
                ans[next].push({t.dist+dist});
                pq.push({next,t.dist+dist});
            }
            else
            {
                if(ans[next].top()>t.dist+dist)
                {
                    ans[next].pop();
                    ans[next].push(t.dist+dist);
                    pq.push({next,t.dist+dist});
                }
            }
        }
    }
}
int main()
{
    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);
        road[a].push_back({b,c});
    }
    Dijkstra();
    for(int i=1;i<=N;i++)
    {
        printf("%d\n",kth[i]);
    }
}

전체 코드이다.