[C++] 백준 1948: 임계경로

문제 이해

- 모든 도로가 일방 통행인 도로이고, 싸이클이 없다 => 사이클이 아닌 방향 그래프(Directed Acyclic Graph)

- 시작 도시부터 도착 도시까지 가능한 모든 경로를 탐색할 예정

- 출발 도시: 들어오는 도로가 0개

- 도착 도시: 나가는 도로가 0개

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 512MB

 

<입력>

- n: 도시의 개수 (1 ~ 10,000, 10^4)

- m: 도로의 개수( 1 ~ 100,000, 10^5)

- 도로의 정보(출발 도시, 도착 도시, 걸리는 시간(1 ~ 10,000, 10^4))

- 출발 도시, 도착 도시

 

<출력>

- 임계 경로의 비용(마지막에 도착하는 사람이 도착하는 시간)

- 이 시간까지 쉬지 않고 움직이는 사람들이 지나가는 도로의 개수

임계경로
위상 정렬을 진행하면 각 작업이 어떠한 순서로 진행되어야 하는지 알 수 있다.
임계경로는 finish에 도달하는데 가장 오래 걸리는 경로를 의미한다.
즉, 방향그래프에서 위상정렬로 순서를 표현하면, 임계경로는 그 중 가장 큰 비용이 드는 경로를 의미한다.

 

문제 풀이

사이클이 아닌 방향 그래프에서 걸리는 시간을 구하는 문제이므로 '위상 정렬 + DP'를 사용했다.

=> 첫 번째 출력인 마지막에 도착하는 시간은 정말 쉽게 구할 수 있었다!

 

 

하지만 두 번째 출력해야 할 도로의 개수에서 헤맸던 문제이다...

30분 정도 고민하여 풀이의 느낌은 감을 잡았는데 구현 방식을 알아내지 못했다.

=> 난이도가 플레티넘인 것에 겁을 먹어 풀이를 제대로 해내지 못한거 같아 아쉽다. 겁먹지 말자.

 

 

필자가 풀이에 접근한 방식

1. 인접 그래프 대신 인접 행렬을 사용해서 풀어보자. > 실패

2. 시간이 오래 걸리는 경로를 모두 찾은 뒤, 겹치는 경로의 개수를 빼자. > 어떻게?

3. 인터넷 풀이 참고(역방향 그래프 이용)

 

 

 

두 번째 출력은 '역방향 그래프'를 이용하면 쉽게 풀 수 있는 문제이다.

첫 번째 출력을 구하며 각 도시까지 도달하는 최대 시간이 DP배열에 구해져 있을텐데,

그 값과 역방향 그래프를 이용해 푸는 문제였다.

 

이때, 중복한 경우를 카운트하지 않도록 bool형 배열을 이용한다.

 

 

<예시>

문제의 예시를 통해 풀어보면

위상 정렬을 통해 dp 배열에는

[1]	[2]	[3]	[4]	[5]	[6]	[7]
0	4	2	3	3	7	12

 

과 값이 들어가있다.

 

예시의 임계 경로는 1>2>6>7과 1>4>6>7이다.

이를 역방향 그래프로 표현하면

7 -> 6 -> 2 -> 1

7 -> 6 -> 4 -> 1

의 경우이다.

 

7 -> 6의 경우를 보자.

임계 경로의 비용(dp[7])은 12이고,

dp[6](7) + 7 -> 6의 비용(5) == 12 이므로 임계 경로로 판단할 수 있다.

 

6 -> 2의 경우 dp[2] + '6 -> 2'의 비용의 합이 dp[6]인 7의 값이 된다면 임계경로일 것이다.

마찬가지로

6 -> 4의 경우 dp[4] + '6 -> 4'의 비용의 합이 dp[6]인 7의 값이 된다면 임계경로일 것이다.

 

 

이 식을 코드로 표현하면 다음과 같다.

 if(dp[now] == dp[next] + cost)

 

 

이 때 중복한 경로는 포함하지 않도록 visited배열을 하나 사용하면 다음과 같은 코드가 결과물로 나온다.

※ rv는 입력받을 때 역방향으로 구성한 그래프이다.

int cnt = 0;
    q.push(end);
    visited[end] = true;

    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        int size = rv[now].size();
        for(int i = 0; i < size; i++){
            int next = rv[now][i].first;
            int cost = rv[now][i].second;

            if(dp[now] == dp[next] + cost){
                cnt++;
                if(visited[next] == false){
                    visited[next] = true;
                    q.push(next);
                }
            } 
        }
    }

    cout<<cnt;

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector <pair<int, int>> v[10005];
vector <pair<int, int>> rv[10005];
int inDegree[10005];
int dp[10005];
bool visited[10005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin>>n>>m;

    for(int i = 0; i < m; i++){
        int a, b, cost;
        cin>>a>>b>>cost;
        v[a].push_back({b, cost});
        rv[b].push_back({a, cost});
        inDegree[b]++;
    }

    int start, end;
    cin>>start>>end;

    //걸리는 시간이 최대인 경우의 시간 구하기.
    queue <int> q;
    q.push(start);

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

        int size = v[now].size();
        for(int i = 0; i < size; i++){
            int next = v[now][i].first;
            int cost = v[now][i].second;
            inDegree[next]--;
            dp[next] = max(dp[next], dp[now] + cost);

            if(inDegree[next] == 0){
                q.push(next);
            }
        }
    }

    cout<<dp[end]<<"\n";

    //걸리는 시간이 최대인 경로의 도로의 개수 구하기.
    //역방향 그래프로 풀기.
    int cnt = 0;
    q.push(end);
    visited[end] = true;

    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        int size = rv[now].size();
        for(int i = 0; i < size; i++){
            int next = rv[now][i].first;
            int cost = rv[now][i].second;

            if(dp[now] == dp[next] + cost){
                cnt++;
                if(visited[next] == false){
                    visited[next] = true;
                    q.push(next);
                }
            } 
        }
    }

    cout<<cnt;

    return 0;
}

 

역방향 그래프도 고려해볼 필요가 있음을 인지시켜준 문제이다!