[BOJ] 5719 : 거의 최단 경로

문제 링크

5719번: 거의 최단 경로 (acmicpc.net)

5719번: 거의 최단 경로

풀이

최단경로로 통하는 길을 모두 제외한 나머지 경로 중에서 갈 수 있는 최단경로를 구하는 문제.

1. 최단경로에 포함되는 정점을 제거하면 길이 있어도 못가기 때문에 안됨

2. 최단경로를 탐색하고 도로를 바로 제거하면 만약 최단경로가 여러개이면서 최단경로끼리

같은 도로를 공유한다면?? 두번째 최단경로는 탐색할 수 없다.

 

=> 그래서 내가 떠올린 아이디어는 탐색한 최단경로에 포함된 한 정점을 기준으로  들어오는 경로가

여러개(두 개 이상)고 다른 정점으로 통하는 경로도 여러개라면?

그때는  그 정점에 연결된 도로 중 최단경로에 포함되는 도로는 지워도 될 것이다.

왜냐 지워도 다른 경로로 이동이 가능하니까.

=> 그 도로는 실제로 지우고 나머지는 Delete라는 벡터에 저장해 뒀다가 나중에 한 번에 지운다

그리고 만약 최단경로에 포함된 정점 중 그러한 정점이 없다면? 아무 도로나 지워도 될 것이라고 생각했다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
const int MAX_N = 500 + 5;
typedef priority_queue <pair<pair<int,int>,pair<int, int>> , vector<pair<pair<int,int>, pair<int, int>>>, greater<pair<pair<int,int>, pair<int, int>>> > Priority_queue;
int N, M;
int S, D;
const int INF = INT_MAX;
vector<int> dist(MAX_N, INF);
vector<pair<int,int>> Before(MAX_N,{-1,-1});
vector<pair<pair<int,int>,bool>> Edge[MAX_N];
vector<pair<int, int>> Delete;
 
void dijkstra(int st, int ed) {
    Priority_queue pq;
    pq.push({ { 0, st },{st,st} }); //{비용, 다음 정점},{이전 도로의 좌표}
    while (!pq.empty()) {
        int now = pq.top().first.second;
        int cost = pq.top().first.first;
        int edge_y = pq.top().second.first;
        int edge_x = pq.top().second.second;
        pq.pop();
        if (dist[now] != INF)
            continue;
        else {
            dist[now] = cost;
            Before[now] = { edge_y, edge_x };
        }
        if (now == ed)
            break;
        for (int i = 0; i < Edge[now].size(); i++) {
            if (Edge[now][i].second) {
                int next = Edge[now][i].first.first;
                int acost = cost + Edge[now][i].first.second;
                if (dist[next] != INF)
                    continue;
                else {
                    pq.push({ {acost,next },{now,i}});//이전 도로의 정보를 pq에 넣어줌{now,i}로
                }
            }
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while (true) {
        cin >> N >> M;
        if (!N && !M) break;
        cin >> S >> D;
        int Min_distance = MAX_N;
        for (int i = 0; i < N; i++) {
            Edge[i].clear();
        }
        for (int i = 0; i <= N; i++) {
            Before[i].first = -1;
            Before[i].second = -1;
        }
        Delete.clear();
        fill(dist.begin(), dist.end(), INF);
        for (int i = 0; i < M; i++) {
            int u, v, p;
            cin >> u >> v >> p;
            Edge[u].push_back({ { v,p },true });
        }
        dijkstra(S, D); //일단 최단경로를 찾는다
        if (dist[D] == INF) { //만약 목적지에 갈 수 없으면 바로 종료
            cout << "-1\n";
            continue;
        }
        else Min_distance = dist[D];
 
        int now_node = D;
        int is_Deleted = false;
        while (true) {
            /* 과거를 추적하면서 거쳐온 도로를 Delete라는 Vector에 넣어줌
            * 나중에 한 번에 도로를 삭제하려는 목적
            * 만약 그 정점까지 도달할 수 있는 경로가 여러개고 그 정점에서 갈 수 있는 정점이 여러개면
            * 그 도로는 일단 하나 삭제함
            */
            int Before_y = Before[now_node].first;
            int Before_x = Before[now_node].second;
            if (Before_y == -1)
                break;
            else if (Before_y == S) {
                if (!is_Deleted && Edge[Before_y].size() != 1) {
                    if (Edge[now_node].size() != 1) {
                        Edge[Before_y][Before_x].second = false;
                        is_Deleted = true;
                    }
                }
                Delete.push_back({ Before_y, Before_x });
                break;
            }
            else {
                if (!is_Deleted && Edge[Before_y].size() != 1) {
                    if (Edge[now_node].size() != 1) {
                        Edge[Before_y][Before_x].second = false;
                        is_Deleted = true;
                    }
                }
                Delete.push_back({ Before_y, Before_x });
                now_node = Before_y;
            }
        }
        if (!is_Deleted) {
            Edge[Before[D].first][Before[D].second].second = false;
        }
        while (true) {
            is_Deleted = false;
            for (int i = 0; i <= N; i++) {
                Before[i].first = -1;
                Before[i].second = -1;
            }
            fill(dist.begin(), dist.end(), INF);
            dijkstra(S, D);
            //반복문을 돌면서 최단경로와 같은 길이의 경로가 또있는지 계속 탐색
            //있으면 그 경로는 또 Delte 벡터에 저장
            if (dist[D] != INF && Min_distance == dist[D]) {
                now_node = D;
                while (true) {
                    int Before_y = Before[now_node].first;
                    int Before_x = Before[now_node].second;
                    if (Before_y == -1)
                        break;
                    else if (Before_y == S) {
                        if (!is_Deleted && Edge[Before_y].size() != 1) {
                            if (Edge[now_node].size() != 1) {
                                Edge[Before_y][Before_x].second = false;
                                is_Deleted = true;
                            }
                        }
                        Delete.push_back({ Before_y, Before_x });
                        break;
                    }
                    else {
                        if (!is_Deleted && Edge[Before_y].size() != 1) {
                            if (Edge[now_node].size() != 1) {
                                Edge[Before_y][Before_x].second = false;
                                is_Deleted = true;
                            }
                        }
                        Delete.push_back({ Before_y, Before_x });
                        now_node = Before_y;
                    }
                }
                if (!is_Deleted) {
                    Edge[Before[D].first][Before[D].second].second = false;
                }
 
            }
            else break;
        }
        if (dist[D] == INF) {
            cout << "-1\n";
            continue;
        }
        for (int i = 0; i < Delete.size(); i++) {
            int Delete_y = Delete[i].first;
            int Delete_x = Delete[i].second;
            Edge[Delete_y][Delete_x].second = false;
        }
        fill(dist.begin(), dist.end(), INF);
        dijkstra(S, D);
        if (dist[D] == INF)
            cout << "-1\n";
        else cout << dist[D] << "\n";
    }
    return 0;
}

코드가 조금 복잡한데, 먼저 맨 처음 다익스트라 알고리즘을 통해 최단경로를 탐색하고 그 경로의 가중치 합을 Min이라는 변수에 저장해뒀다. 최단경로에 포함된 도로 중 아까 말한 조건을 만족하는 도로는 실제로 값을 false로 바꿔 지워주고 나머지 도로는 Delete라는 벡터에 저장해뒀다.

다시 다익스트라 알고리즘을 실행했을 때 아까 저장해둔 Min값과 가중치의 합이 같은 경로가 아직 존재한다면 그 경로도 지워야한다. => 이 과정을 계속 반복. Min과 값이 같은 경로가 존재하지 않을 때 까지.

최단경로가 더 이상 없다고 판단되면 그 때 Delte 벡터에 저장되어 있던 도로를 모두 false로 바꿔 도로를 지운다.

그 후 다익스트라 알고리즘을 한 번 더 돌려서 나온 값이 INF라면 -1출력 아니면 해당값 출력