[정답이 아니라 풀이 기록입니다.]
n개의 도시가 가중치가 있는 도로들로 연결되어있다. 이 때 1~n번째 줄에 1번 도시에서 출발해서 1~n번 도시로 가는 경로중 k번째로 짧은 경로의 길이를 출력하여라.
접근
- 모든 노드에서 1번 노드에서 출발한 k번째 최단경로를 찾아야합니다.
- 같은 노드도 여러번 방문할 수 있습니다.
- 간선은 유향입니다.
구현
다익스트라
음수간선도 없고, 모든 노드에서 특정 노드에서 출발한 최단경로를 찾는데는 다익스트라가 최적이죠
다익스트라를 구현해봅시다.
while (!pq.empty()) {
int node = pq.top().second;
ll cost = pq.top().first;
pq.pop();
if(cost > D[node]){
continue;
}
for (int i = 0; i < v[node].size(); i++) {
int t = v[node][i].second;
ll w = v[node][i].first;
if(D[t] > cost + w){
D[t] = cost + w;
pq.push({cost + w ,t });
}
}
}그냥 일반적인 우선순위큐 다익스트라입니다.
다익스트라의 변형
여기서 이제 저희는 노드를 중복 방문할 수 있습니다.
비용이 이전보다 작은 경우에만 갱신하던 부분을 제거합니다.
while (!pq.empty()) {
int node = pq.top().second;
ll cost = pq.top().first;
pq.pop();
for (int i = 0; i < v[node].size(); i++) {
int t = v[node][i].second;
ll w = v[node][i].first;
D[t] = cost + w;
pq.push({cost + w ,t });
}
}그리고 K번째 최단경로를 저장해야하기에 D[t]에 바로 저장하는 것이 아니라 리스트 같은 곳에 저장해서 k번째를 찾아내야합니다.
while (!pq.empty()) {
int node = pq.top().second;
ll cost = pq.top().first;
pq.pop();
for (int i = 0; i < v[node].size(); i++) {
int t = v[node][i].second;
ll w = v[node][i].first;
//D[t] = cost + w; 리스트로 변경...?
pq.push({cost + w ,t });
}
}리스트를 쓰고자하면 쓸 수 있긴 하지만 무한루프가 생길 수도 있고 종료 조건이 안보이네요.
딱 k번째 경로만 구해봅시다.
k번째 경로
생각해보면 k번째 경로는 가장 짧은 최단 경로 다음으로 k번째 짧은 경로입니다.
즉, 경로는 무조건 딱 k개만 리스트에 저장하고 관리하면 됩니다.
1번에서 M번으로 가는 새로운 경로의 길이가 들어오고 그 길이가 L이라 가정하겠습니다.
만약 현재 M번 노드의 리스트 사이즈가 K보다 작다면 그냥 리스트에 넣으면 됩니다.
리스트 사이즈가 딱 K라면 리스트의 원소중 가장 거리가 긴 원소와 비교해봅니다.
만약 리스트의 가장 거리가 긴 원소가 L보다 작다면 L보다 짧은 경로가 이미 K개 있는 것 입니다.
그렇기에 L은 답을 구하는데 필요가 없고, 또 M번과 연결된 다른 노드들도 L보다 짧은 K개의 경로들로 K개의 거리를 이미 구했을 것이기에 갱신할 필요도 없게 됩니다.
그리고 만약 리스트의 가장 길이가 긴 원소가 L보다 작다면, 이 L은 K개의 경로에 포함 될 수 있습니다.
그렇기에 리스트의 가장 길이 긴 원소를 빼내고 L을 집어 넣습니다.
또 이 M번 노드와 연결된 노드들도 갱신이 필요하기에 우선순위 큐에 집어 넣어 줍니다.
생각해보면 가장 길이가 긴 것을 꺼내고 새로운 것을 넣는다
이것에 최적화 된것은 내림차순으로 정렬된 우선순위 큐입니다.
이 문제의 핵심은 거리를 우선순위 큐로 저장하는 것입니다.
//ll == long long
priority_queue<ll> D[1001];
//STL 우선순위큐는 기본이 내림차순입니다.
while (!pq.empty()) {
int node = pq.top().second;
ll cost = pq.top().first;
pq.pop();
for (int i = 0; i < v[node].size(); i++) {
int t = v[node][i].second;
ll w = v[node][i].first;
if (D[t].size() == k) {//거리가 이미 K개 라면
if (D[t].top() > cost + w) {//거리 중 가장 긴 것과 새로운 거리 비교
D[t].pop();//만약 새로운 거리가 더 짧다면 가장 긴 것 빼냄
D[t].push(cost+w);//새로운 거리 넣음
pq.push({cost+w,t});//연결된 노드도 갱신이 필요하기에 pq에 넣음
}
}
else {//거리가 k개보다 작다면
D[t].push(cost + w);//새로운 거리 넣음
pq.push({ cost + w,t });//연결된 노드도 갱신이 필요하기에 pq에 넣음
}
}
}
주의하실점은 처음에 1번 노드의 거리, 즉 D[1]에 0을 넣어주고 시작해야합니다.
답 출력
위와 같이 구현한다면 D[i]에 i번 노드의 거리가 저장되어있습니다.
이때 만약 D[i]의 사이즈가 k보다 작다면 i번 노드는 k번째 최단경로가 없는 것입니다.
그리고 D[i]의 사이즈가 k라면 D[i]의 top에 i번 노드의 k번째 최단경로의 거리가 저장되어 있기에 출력해줍니다.
for (int i = 1; i <= n; i++) {
if (D[i].size() < k) {
printf("-1\n");
}
else {
printf("%lld\n",D[i].top());
}
}마무리
거리를 우선순위큐에 저장한다는 걸 떠올리기가 어려운 문제인 것 같습니다.
저는 우선순위큐로 k개를 취하는걸 이 문제 -(링크)를 푼 기억을 떠올려서 구현했습니다.
끝
