[ 백준 1948 ] 임계경로 (C++)

백준의 임계경로(1948) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 문제에서 구하고자 하는 값들에 대해서 부터 정리를 해보자.

우리는 2가지를 구해야 한다.

첫 번째는, "모든 사람들이 만나는 시간" 을 구해야 한다. 이 때, 사람들은 가능한 모든 경로를 다 탐색한다고 문제에서 주어졌다.

즉 ! 시작점에서 도착점까지 가는데 하나의 경로가 아닌 수 많은 경로가 존재할 수 있다. 물론, 각 경로마다 도착점까지 가는데

걸리는 시간 또한 다를 것이다. 이런 상황속에서 "모든 사람들이 만나는 시간"을 구해야 하는 것이다.

다르게 이야기 해보자면, "도착점에 가장 오래 걸리는 사람이 도착하는 시간"을 구하면 된다. 예를 들어서 A점에서 B점까지 가야 하는데 1번 경로를 통해서 가면 1초가, 2번 경로를 통해서 가면 2초가, 3번 경로를 통해서 가면 3초가 걸리게 된다고 가정해보자.

그럼 이 때, "모든 사람들이 만나는시간"은 몇 초일까 ? 바로 3초일 것이다. 왜냐하면 1번 경로를 통해서 가는 사람은 1초만에

도착을 할 것이고, 2번 경로를 통해서 가는 사람은 2초, 3번 경로를 통해서 가는 사람은 3초가 걸릴 것이기 때문에 "모든 사람들이

만나는 시간" 은 3초가 된다. 문제에서 "어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다." 라는 말이 있는데,

이 말은 위의 경우에서 3번경로를 통해 오는 사람을 이야기한다. 즉, "도착점에 가장 늦게 도착했을 때, 걸리는 경로의 시간"을

구해야 한다 !

두 번째는, "1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수" 를 구해야 한다. 우리는 첫 번째 경우에 대한 설명을 통해서

"1분도 쉬지 않고 달려야 하는 사람들이 지나는 경로"가 곧 "도착점에 가장 늦게 도착하는 경로"를 의미한다는 것을 알고 있다.

그대로 대입해보면, "도착점에 가장 늦게 도착하는 경로로 움직일 때, 지나는 도로의 수" 를 구해야 한다는 것을 쉽게 알 수 있다.

그럼 이제 첫번째 경우 두 번째 경우를 나눠서 구해보자.

1. 모든 사람들이 만나는 시간 구하기 = 도착점에 가장 늦게 도착했을 때, 걸리는 경로의 시간 구하기

문제에 보면, 모든 도로가 "일방통행" 이라고 되어 있다. 즉 ! 입력으로 a b c (정점 a와 b를 연결하는 도로는 c만큼의 시간이 걸립니다) 라고 주어졌을 때, 우리는 이 도로를 건너기 위해서는 한 가지 조건을 만족해야 한다.

예를 들어서 [ 1 , 2 , 3 ] , [ 2 , 3 , 4 ] 와 같은 입력이 주어졌다고 생각해보자.

풀어서 써보면 1번도시와 2번도시를 연결하는 도로를 지나는데 3만큼의 시간이 걸립니다.

2번 도시와 3번도시를 연결하는 도로를 지나는데 4만큼의 시간이 걸립니다. 가 된다.

그럼 이 때, 1번 도시에서 3번 도시로 가기 위해서는 어떤 조건이 필요할까 ??

바로 "1번 도시를 지나치고, 2번도시를 지나쳐야" 비로소 3번 도시로 갈 수 있다는 것이다. 이러한 점에서 본인은 "위상정렬"로

이 부분을 접근해보았다. 정리해서 이야기해보면 "특정 도시 x를 가기 위해서는, x로 가기 위해서 필요한 그 전의 도시들을

모두 방문해야만 갈 수 있다". 즉, 일의 순서를 정하는 것과 마찬가지로, 우선적으로 먼저 거쳐야할 도시들이 존재한다는

것이다. 따라서 이 부분을 "위상정렬"을 통해서 구현해 주었다. 위상정렬을 구현하기 위해서 입력과 동시에, "x번 도시를 가기

위해서 그 전에 우선적으로 거쳐야할 도시의 갯수"를 저장해주었다.

2. 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 갯수 구하기 = 도착점에 가장 늦게 도착하는 경로의 도로의 수 구하기

생각보다 조금 까다로웠던 부분이다. 이 부분은 역으로 계산하면서 한번 값을 구해보았다.

먼저 간단하게 예를 들어서 한번 알아보자.

위와 같은 상황을 생각해보자. 우리는 1번 도시에서 4번도시로 가야한다.

먼저, 첫 번째 부분을 구현하면서 구한 "각 도시에 도착하는 가장 오래 걸리는 시간"을 계산해보면 [ 0 , 3 , 4 , 5 ] 가 나올 것이다.

그럼 이제 가장 긴 경로를 한번 찾아보자. 가장 긴 경로라는 것은 "해당 도로로 지났을 때, 남은 시간이 해당 도시의 시간과 일치"

한다고 표현할 수 있다. 조금 더 구체적으로 이야기해보면, 예를 들어서 위의 경우에서 4번도시에서 역으로 출발한다고 생각했을

때, 4번 도시에서 3번도시로 가는 경우를 생각해보자.

3번도시로 가는 가장 오래 걸리는 시간은 '4초(1 → 2 → 3)' 이다.

4번도시로 가는 가장 오래 걸리는 시간은 '5초(1 → 2 → 4)' 이다.

그럼, 4번도시에서 3번도시로 가게되면, 걸린시간은 5초 - 2초(3 - 4를 잇는 도로) = 3초가 된다.

즉, 4번도시에서 3번도시로 가는 도로를 지나게 되면 '4번 도시로 가는데 남은시간'이 3초가 된다.

그런데 ? 3번도시는 가장 오래된 경로로 오게되면 '4초'가 걸리게 된다. 즉, 이 '3초'라는 시간과 '4초'라는 시간이 다르다는 것을

통해서 "이 경로는 가장 오래걸리는 경로가 아니다" 라는 것을 알 수 있다. 저 경로가 가장 오래 걸리는 경로에 포함된 경로라면,

4번도시에서 3번도시로 왔을 때, 남은 시간이 '3번 도시로 오는데 걸리는 시간'과 일치할 것이다. 즉 ! 일치하는 않는다는 것을

통해서, "3번 도시로는 더 오래 걸리는 다른 경로가 있구나!" 라는 것을 알 수 있다.

그럼 4번도시에서 2번 도시로 오는 경우를 한번 보자. 마찬가지로 4번도시에서 2번도시로 가게되면 '2초'만큼 빠지게 되므로,

5초 - 2초 = 3초가 된다. 그런데 이번에는 아까와는 다르게, "2번 도시로 가는데 가장 오래 걸리는 경로를 지났을 때 걸리는 시간은

3초" 이기 때문에 이 값이 일치하게 된다.

즉 ! 값이 일치하기 때문에 "이 경로를 통해서 간다면, 그 루트가 가장 오래 걸리는 경로구나 !" 라는 것을 알 수 있다.

이러한 방법으로 역으로 경로를 파악하였다.

그리고 또 하나 고려해 줘야 할 것은 "중복된 도로 탐색" 이다. 문제에서 주어진 예제입력의 경우를 적어보면 답이 [ 12 , 5 ] 가

나오게 되는데, 이 '12'가 걸리는 경로를 적어보면 1 → 2 → 6 → 7 혹은 1 → 4 → 6 → 7 로 오게 되는 경우 가장 오래걸리는

루트로써 12초가 걸리게 된다. 도로의 수를 Count해보면,

1 → 2 , 2 → 6 , 6 → 7 , 1 → 4 , 4 → 6 , 6 → 7 이렇게 6개가 존재한다. 하지만 6 → 7은 중복된 도로이다. 즉 ! 카운트를

2번을 해주면 안되고 한번만 해줘야 하는 것이다. 따라서 이렇게 방문하지 않은 도시에 대한 체크를 해주면서 진행을

해주어야 한다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 10010
using namespace std;
 
int N, M, Start, End, Road_Cnt;
int Entry[MAX], Time[MAX];
bool Visit[MAX];
vector<pair<int, int>> Road[MAX], R_Road[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Road[a].push_back(make_pair(b, c));
        R_Road[b].push_back(make_pair(a, c));
        Entry[b]++;
    }
    cin >> Start >> End;
}
 
void Find_Dist(int S)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(S, 0));
    
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Cur_Time = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < Road[Cur].size(); i++)
        {
            int Next = Road[Cur][i].first;
            int nTime = Road[Cur][i].second;
 
            Time[Next] = Bigger(Time[Next], Cur_Time + nTime);
            Entry[Next]--;
 
            if (Entry[Next] == 0) Q.push(make_pair(Next, Time[Next]));
        }
    }
}
 
void Find_Longest_Road(int E)
{
    queue<int> Q;
    Q.push(E);
    Visit[E] = true;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front();
        Q.pop();
 
        for (int i = 0; i < R_Road[Cur].size(); i++)
        {
            int Prev = R_Road[Cur][i].first;
            int PrevTime = R_Road[Cur][i].second;
 
            if (Time[Cur] - PrevTime == Time[Prev])
            {
                Road_Cnt++;
                if (Visit[Prev] == false)
                {
                    Visit[Prev] = true;
                    Q.push(Prev);                    
                }
            }
        }
    }
}
 
void Solution()
{
    Find_Dist(Start);
    Find_Longest_Road(End);
    for (int i = 1; i <= N; i++) cout << Time[i] << " ";
    cout << endl;
 
    cout << Time[End] << endl << Road_Cnt << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}