백준 5719 거의 최단 경로 - C++, 다익스트라, BFS

5719번: 거의 최단 경로

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define MAX 501
using namespace std;

int n, m, start, finish;
int inputFrom, inputTo, inputCost;
int city[MAX];
bool isFast[MAX][MAX];
bool visit[MAX];

void Djik(vector<pair<int, int> > road[]){
    for(int i = 0; i <= n; i++)
        city[i] = 999999999;

    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, start));
    city[start] = 0;

    while (!q.empty()){
        int cur = q.top().second;
        int curCost = -q.top().first;
        q.pop();

        if(city[cur] < curCost)
            continue;

        for(int i = 0; i < road[cur].size(); i++){
            int nextCur = road[cur][i].first;
            int nextCost = road[cur][i].second;

            // 빠른길 건너뛰기
            if(isFast[cur][nextCur] == true)
                continue;

            if(city[nextCur] > curCost + nextCost){
                city[nextCur] = curCost + nextCost;
                q.push(make_pair(-city[nextCur], nextCur));
            }
        }
    } 
}

void FastRoadSearch(vector<pair<int, int> > inverserRoad[]){
    queue<int> q;
    q.push(finish);

    while (!q.empty()){
        int cur = q.front();
        q.pop();

        if(visit[cur] == true)
            continue;
        if(cur == start)
            continue;
        
        visit[cur] = true;
        for(int i = 0; i < inverserRoad[cur].size(); i++){
            int prev = inverserRoad[cur][i].first;

            if(city[prev] + inverserRoad[cur][i].second == city[cur]){
                isFast[prev][cur] = true;
                q.push(prev);
            }
        }
    } 
}

int main(){
    while(true){
        // 초기화 해야 할 것들
        // city(거리값저장 배열), isFast
        memset(isFast, false, sizeof(isFast));
        memset(visit, false, sizeof(visit));
        // 입력
        cin >> n >> m;
        if(n == 0 && m == 0)
            break;
        cin >> start >> finish;

        // 경로 저장
        vector<pair<int, int> > road[MAX];
        vector<pair<int, int> > inverseRoad[MAX];
        
        
        while(m--){
            cin >> inputFrom >> inputTo >> inputCost;
            road[inputFrom].push_back(make_pair(inputTo, inputCost));
            inverseRoad[inputTo].push_back(make_pair(inputFrom, inputCost));
        }
        // 탐색
        Djik(road);
        FastRoadSearch(inverseRoad);
        Djik(road);

        if(city[finish] == 999999999)
            cout << "-1\n";
        else
            cout << city[finish] << '\n';
    }
    
}

---

 이전 백준 1299번 문제를 풀이하려다가 설명이 너무 부족한 문제라 다른 문제를 추천받아 풀게 된 문제입니다. 문제를 봤을 때 생각을 한건 아래 3가지 입니다.

 

1. 처음에는 다익스트라로 최소 길을 구하자!

2. 그런 다음 경로 역추적을 통해서 경로를 뽑아내고 이 길은 false 처리를 하자!

3. 다시 다익스트라를 도는데 false인 길은 피하자!

 

 로 순서를 구상을 했고 11779번 문제(풀이 : https://husk321.tistory.com/159)에서 한대로 배열을 통해서 경로 역추적을 하려고 했으나 생각보다 잘 안되었습니다. 아마 배열의 초기화와 관련한 문제였던 것 같습니다. 그래서 이 방식의 추적은 그만두고 다른곳에서 아이디어를 얻은 것인데 '입력시 역방향 경로를 받아오고 이후 BFS로 탐색'을 하는 것이었습니다. 그 결과 위 FastRoadSearch 함수가 나오게 되었습니다.

  + 찾아보니 BFS가 아닌 DFS가 더 효율적으로 보였습니다.

 

void Djik(vector<pair<int, int> > road[]){
    for(int i = 0; i <= n; i++)
        city[i] = 999999999;

    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, start));
    city[start] = 0;

    while (!q.empty()){
        int cur = q.top().second;
        int curCost = -q.top().first;
        q.pop();

        if(city[cur] < curCost)
            continue;

        for(int i = 0; i < road[cur].size(); i++){
            int nextCur = road[cur][i].first;
            int nextCost = road[cur][i].second;

            // 빠른길 건너뛰기
            if(isFast[cur][nextCur] == true)
                continue;

            if(city[nextCur] > curCost + nextCost){
                city[nextCur] = curCost + nextCost;
                q.push(make_pair(-city[nextCur], nextCur));
            }
        }
    } 
}

 코드 설명을 남기자면 기존의 다익스트라와 비슷하지만 배열을 여러번 사용하게 되니 목적지까지 비용을 담는 city 배열을 함수 처음에 초기화를 해줘야 합니다. 또한 isFast[cur][nextCur]을 통해서 처음 다익스트라를 하고 나서 얻어진 빠른 경로라고 하면 continue로 건너뛰도록 했습니다.

void FastRoadSearch(vector<pair<int, int> > inverserRoad[]){
    queue<int> q;
    q.push(finish);

    while (!q.empty()){
        int cur = q.front();
        q.pop();

        if(visit[cur] == true)
            continue;
        if(cur == start)
            continue;
        
        visit[cur] = true;
        for(int i = 0; i < inverserRoad[cur].size(); i++){
            int prev = inverserRoad[cur][i].first;

            if(city[prev] + inverserRoad[cur][i].second == city[cur]){
                isFast[prev][cur] = true;
                q.push(prev);
            }
        }
    } 
}

 다익스트라를 한번 하고 나서 빠른 길 탐색을 하는 FastRoadSearch함수는 입력에서 있는 inverseRoad를 건네받아 이를 통해서 경로를 역추적하게 됩니다. 아직 city 배열이 초기화 안된 상태이므로 이걸 이용해서 [ 1~n-1 까지의 비용 + n-1~n 까지의 비용 = 1~n까지 비용 ] 인지를 검사해 bfs로 탐색을 하게 됩니다. 이제 2차원 bool배열을 true로 변경해 다음 다익스트라에서 최단 거리를 제외하고 탐색을 하게 합니다.