[임계경로/P5/Python3, C++]

1948번 임계경로 P5

 

문제
월드 나라는 모든 도로가 일방통행인 도로이고, 사이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트하여라. 출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

입력
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는 데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다. 그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다. 모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.

출력
첫째 줄에는 이들이 만나는 시간을, 둘째 줄에는 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 출력하여라.

 

 

그래프 이론, 그래프 탐색, 위상 정렬, 방향 비순환 그래프

 

DP를 통해 각 도시의 도착 시간을 기록하였다.

위상 정렬을 통해 출발 도시를 구하고 도착 지점까지 모든 경로를 탐색했다.

 

역방향 경로라는 아이디어를 이용하여 위 문제를 풀이하였다.

 

도착 도시의 도착 시간을 Time1, 도착 도시 이전 도시들의 도착시간을 Time2, 도로의 시간을 cost라고 하자.

만일 이전 도시에서 한 번도 안쉬고 와야 하는 상황이라면, Time1 == Time2 + cost일 것이다.

이를 역방향 경로를 사용하여 구하였다.

 

시간 복잡도의 경우 위상 정렬은 모든 정점과 간선을 확인해야하기 때문에 O(V+E)이다.  V: 정점, E:간선

역방향으로 BFS를 조건에 맞는 간선만 추가로 확인을 진행한다.

즉, 최악의 경우 O(V+2E)가 된다.  1V인 이유는, 도착 정점을 따로 구하지 않아도 되기 때문이다.

 

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

dp = [0] * (n+1)
cnts = [0] * (n+1)
add = [False] * (n+1)
routes = [[] for _ in range(n+1)]
reverse_route = [[] for _ in range(n+1)]

for i in range(m):
    s, e, cost = map(int, sys.stdin.readline().split())
    routes[s].append((e, cost))
    cnts[e] += 1
    reverse_route[e].append((s, cost))

sv, ev = map(int, sys.stdin.readline().split())
cnt = 0

q = deque()
for i in range(1, n+1):
    if cnts[i] == 0 and i != ev:
        q.append(i)
while q:
    v = q.popleft()
    for e, cost in routes[v]:
        dp[e] = max(dp[e], dp[v] + cost)
        cnts[e] -= 1
        if cnts[e] == 0:
            q.append(e)

q = deque()
q.append(ev)
while q:
    v = q.popleft()
    for e, cost in reverse_route[v]:
        if dp[e] + cost == dp[v]:
            cnt += 1
            if add[e] == False:
                add[e] = True
                q.append(e)
            
print(dp[ev])
print(cnt)

 

 

 

c++의 문법은 익숙지 않아, 보기에 조금 엉성한 부분이 있을 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;
vector<pair<int, int>> routes[10001];
vector<pair<int, int>> rev_routes[10001];
int in_cnt[10001] = {0,};
int dp[10001] = {0,};
bool visit[10001] = {0, };

int main()
{
    int n, m;
    cin>>n;
    cin>>m;
    

    int s, e, c;
    while (m--)
    {
        cin>>s>>e>>c;
        routes[s].push_back(make_pair(e,c));
        rev_routes[e].push_back(make_pair(s,c));
        ++in_cnt[e];
    }
    int start, end;
    cin>>start>>end;

    deque<int> dq;
    for (int i = 1; i<n+1; ++i)
    {
        if (in_cnt[i] == 0)
            dq.push_back(i);
    }
    
    while (!dq.empty())
    {
        s = dq.front();
        dq.pop_front();
        for (int i = 0; i < routes[s].size(); ++i)
        {
            e = routes[s][i].first;
            c = routes[s][i].second;
            dp[e] = max(dp[e], dp[s] + c);
            if (--in_cnt[e] == 0)
                dq.push_back(e);
        }
    }

    int cnt=0;
    dq.push_back(end);
    
    while (!dq.empty())
    {
        s = dq.front();
        dq.pop_front();
        for (int i = 0; i < rev_routes[s].size(); ++i)
        {
            e = rev_routes[s][i].first;
            c = rev_routes[s][i].second;
            if (dp[e] == dp[s]-c)
            {
                cnt++;
                if(!visit[e])
                {
                    visit[e] = true;
                    dq.push_back(e);
                }
            }
        }
    }
    
    cout<<dp[end]<<'\n'<<cnt;
}

 

---

 

문제의 아이디어도 참신했고, 역으로 추적하는 부분이 재미있었다.

위상 정렬에 대해 공부를 하고 있다면 추천하고 싶은 문제이다.