백준 5719 - 거의 최단 경로(C++, 복습)

문제 링크입니다. https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

다익스트라 + BFS를 이용한 문제입니다.

 

어떠한 최단 경로가 있을 때, 해당 경로를 지우고 난 뒤의 다음 최단 경로를 찾는 문제입니다.

최단 경로를 찾는 것은 간단합니다. 다익스트라 알고리즘을 사용하면 찾을 수 있습니다.

 

그 다음인 최단 경로를 지우는 것이 문제인데, 이는 BFS를 사용하면 됩니다.

 

BFS를 통해 최단 경로를 지우기 전에, 다익스트라를 사용하면서 연결된 정점들을 저장해줘야합니다.

 

X점에서 Y점을 최단 경로로 갈 수 있을 때, Y점에 X점을 저장해줍니다. 같은 비용으로 도달할 수 있다면 여러개를 저장해줍니다.

 

정점의 방향을 역방향으로 저장하면서 BFS 탐색에서는 도착점에서 역추적하는 방식으로 간선을 지워주면 됩니다.

(예시 입력을 직접 그려보시면 이해하시는게 쉬울 겁니다!)

 

BFS 탐색을 할 때는, Y점으로 X점을 찾을 수 있을 것입니다. 

그렇지만, 역방향으로 값을 저장을 해줬기에, 간선을 지울 때는 [X][Y]점으로 지워야합나다.

 

최단 경로를 지운 뒤, 다시한번 다익스트라를 이용해 2번째 최단 경로를 찾고, 정답을 출력해줍니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define LL long long int
#define INF 987654321

using namespace std;

int N, M;
int start, finish;
vector<P> connect[501];
vector<int> way[501];
int Distance[501];
int check[501];

void reset_all(){
    memset(connect, 0, sizeof(connect));
    memset(way, 0, sizeof(way));
    memset(Distance, 127, sizeof(Distance));
    memset(check, 0, sizeof(check));
}

void Dijstra(int X){
    priority_queue<P> q;
    q.push({-0, X});
    Distance[X] = 0;
    while(!q.empty()){
        int x = q.top().S;
        int cost = -q.top().F;
        q.pop();
        if(Distance[x] < cost) continue;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int n_cost = cost + connect[x][i].S;
            if(connect[x][i].S == -1) continue; // 최단거리로 지워진 간선은 건너뛴다.
            if(Distance[xx] > n_cost){
                Distance[xx] = n_cost;
                q.push({-n_cost, xx});
                way[xx].clear(); // 새로운 최단거리가 있음으로 이전 것을 초기화한다.
                way[xx].push_back(x); // 새로운 최단거리 노드를 넣는다.
            }
            else if(Distance[xx] == n_cost){ // 같은 비용이라면, 최소 거리가 더 있다는 의미이다.
                way[xx].push_back(x);
            }
        }
    }
}


void bfs(int X){
    queue<int> q;
    q.push(X);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(check[x] != 0) continue;
        check[x] = 1;
        for(int i = 0; i < way[x].size(); i++){
            int xx = way[x][i];
            for(int j = 0; j < connect[xx].size(); j++){
                if(connect[xx][j].F == x) connect[xx][j].S = -1; // 간선을 지워준다.
            }
            q.push(xx);
        }
    }
}

void solve(){
    int Ans = Distance[start];
    Dijstra(start);
    bfs(finish); // 최단거리가 되는 노드들을 저장했음으로 BFS 통해 탐색해서 지워준다.
    memset(Distance, 127, sizeof(Distance));
    Dijstra(start);
    if(Distance[finish] == Ans) cout << "-1" << "\n";
    else cout << Distance[finish] << "\n";
}

int main() {
    cin.tie(0);
    cout.tie(0);
    while(1){
        reset_all();
        cin >> N >> M;
        if(N == 0 && M == 0) break;
        cin >> start >> finish;
        for(int i = 1; i <= M; i++){
            int x, y, cost;
            cin >> x >> y >> cost;
            connect[x].push_back({y, cost});
        }
        solve();
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요