백준 1948번: 임계경로 (C++)

https://www.acmicpc.net/problem/1948

1948번: 임계경로

---

Solved By: Topological Sort or Dijkstra

 

우선적으로 최장 경로를 구해야 하기 때문에 Dijkstra가 떠올랐습니다.

>> 가중치들을 음수로 바꾸어 최장 경로를 구하는 테크닉 사용

 

+ Topological Sort를 사용하여 최장 경로를 구할 수 있습니다.

Topological Sort의 기본 원리를 기억하며 문제를 풀어갑니다.

 

[기본 원리]

일의 순서를 구하기 위해 nextNode들을 탐색해나가며 indegree가 0이 되는 node를 Queue에 담으면 됩니다.

[사용된 테크닉]

그 과정에서 해당 nextNode까지의 경로 값을 최댓값으로 구해나가면 됩니다.

>> 이 테크닉도 기억해두어야겠습니다.

 

>> 결론적으로는 Topological Sort를 사용한 방법이 더 빨랐습니다.

 

하지만, 최장 경로까지는 구할 수 있었지만 제일 문제는 도로의 개수였습니다.

경로 역추적을 하려니 Node를 향해 들어온 prevNode들이 꽤 있을 것이고, 어떤 prevNode들이 최장 경로를 결정짓는 Node인지는 모릅니다.

 

구글링 하다가 발견한 솔루션은 충격이었습니다. 역방향 BFS를 사용하는 것입니다. 더 충격적인 건 역방향 BFS 안에서 도로를 카운트하는 기준입니다.

if(dist[now] - prevCost == dist[prev]){
	cnt++;
}

도착점부터 시작하여 now까지 온 최대 경로 값에서 now와 prev 사이의 값을 뺐을 때, prev까지의 최대 경로 값이 같다면 prev를 거쳐서 온 노드라고 인식하는 것입니다. 아이디어가 너무 멋집니다..

 

물론 이를 위해서는 역방향 인접배열이 필요하고, 또한 똑같은 도로를 카운트하지 않기 위해 중복 체크 배열이 필요합니다.

예를 들면 최장 경로를 유발하는 두 가지 경로가 있다고 합시다.

 

1 -> 2 -> 3 -> 5 -> 6

1 -> 2 -> 4 -> 5 -> 6

 

문제에서와 같이 중복된 도로는 체크하지 않습니다. 6부터 시작하여 (5, 6), (3, 5), (2, 3), (1, 2)의 도로를 점유하고, 다른 하나는 (5, 6), (4, 5), (2, 4), (1, 2) 이 과정에서 BFS에 의하면 (5, 6)은 상관없어도 도로가 다시 맞물리는 과정인 (1, 2)가 BFS가 중복체크를 하지 않는다면 새로운 도로로 알고, 체크할 것입니다. 그렇기 때문에 현재 Queue 안에 어떤 node가 들어있다면 Queue에 Push를 하지 않기 위해 중복 체크를 해주는 것입니다.

 

#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define INF 1e9
#define MAX 10001
using namespace std;

int n, m;
int s, e;
vector<pii> adj[MAX];
vector<pii> radj[MAX];
int indegree[MAX];

vector<int> dijkstra(int node){
    queue<int> q;
    q.push(node);
    vector<int> dist(n + 1, INF);
    dist[node] = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].first;
            int nextCost = adj[now][i].second;
            
            if(dist[now] + nextCost < dist[next]){
                dist[next] = dist[now] + nextCost;
                q.push(next);
            }
        }
    }
    
    return dist;
}

vector<int> topologicalSort(int s){
    queue<int> q;
    q.push(s);
    vector<int> dist(n + 1);
    dist[s] = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].first;
            int nextCost = adj[now][i].second;
            
            dist[next] = max(dist[now] + nextCost, dist[next]);
            
            if(--indegree[next] == 0){
                q.push(next);
            }
        }
    }
    
    return dist;
}

int rbfs(int node, vector<int>& dist){
    queue<int> q;
    q.push(node);
    int cnt = 0;
    // 예제 1 처럼 6 -> 7 같은 중복 경로가 생길 수 있으므로
    // 방문 체크 확인
    vector<bool> visited(n + 1);
    visited[node] = true;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < radj[now].size(); i++){
            int prev = radj[now][i].first;
            int prevCost = radj[now][i].second;
            
            // 값이 일치한다면 prev를 거쳐오는 경로가
            // 제일 오래 걸리는 경로라는 사실을 이용하여 문제를 품
            if(dist[now] - prevCost == dist[prev]){
                cnt++;
                if(visited[prev] == false){
                    visited[prev] = true;
                    q.push(prev);
                }
            }
        }
    }
    
    return cnt;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].push_back({b, w});
        radj[b].push_back({a, w});
        indegree[b]++;
    }
    
    cin >> s >> e;
    
    /*
    // dijkstra 음수 가중치로 넣어두고, 최장 길이 구하기
    // 사이클이 발생할 일이 없으므로 가능함.
    auto dist = dijkstra(s);
    for(int i = 0; i < dist.size(); i++) dist[i] = -dist[i];
    */
    
    auto dist = topologicalSort(s);
    
    cout << dist[e] << '\n';
    
    cout << rbfs(e, dist);
    return 0;
}