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

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

1948번: 임계경로

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/72

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

 

먼저 최장 거리를 얻는 방법은 다음과 같습니다.

 

1. queue에 시작 노드를 넣고 bfs를 시작합니다.

 

2. 위상 정렬 알고리즘을 이용하여 해당 노드까지 오는 모든 길의 걸리는 시간 중 가장 오래 걸리는 시간을 dist 배열에 저장해줍니다.

 

3. 현재 노드까지 오는 모든 길을 탐색하였으면 queue에 넣어줍니다.

 

4. 마지막 노드에 도착했을 때 거리를 return 해주면 최장 거리를 얻을 수 있습니다.

 

이 최장 거리를 이용하여 오는데 지나온 도로를 찾을 수 있습니다.

 

마찬가지로 bfs를 통해 (현재 노드까지 오는데 걸리는 거리 - 다음 노드까지의 거리 == 다음 노드까지의 최장 거리) 일 때 그 도로는 최장 거리로 가는 도로에 포함되므로 ret에 1을 더해줍니다.

 

방문했던 노드에는 다시 방문하면 안 되므로 visited배열을 통해 재방문을 제한해줍니다.

 

[ 소스 코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int n, m;
int from, to;
vector<node> list[10001];
vector<node> r_list[10001];
int cnt[10001], dist[10001];
int visited[10001];
 
 
int Longest_dist(int from)        //가장 오래걸리는 시간 구하기
{
    queue<node> q;
    q.push({ from, 0 });
 
    while (!q.empty())
    {
        int cur = q.front().to;
        int cDist = q.front().dist;
        q.pop();
 
        if (cur == to) {
            return cDist;
        }
 
        for (int i = 0; i < list[cur].size(); i++) {
            int next = list[cur][i].to;
            int nDist = list[cur][i].dist;
 
            cnt[next]--;
            dist[next] = max(dist[next], cDist + nDist);    //다음 노드까지 갈 수 있는 최대 거리
 
            if (cnt[next] == 0) {    //다음 노드까지 갈 수 있는 모든 방법으로 갔을 때
                q.push({ next,dist[next] });
            }
        }
    }
}
 
int Find_road(int max)                //최대 거리로 갈 수 있는 도로 찾기
{
    int ret = 0;
 
    queue<node> q;
    q.push({ to, max });
 
    while (!q.empty())
    {
        int cur = q.front().to;
        int cDist = q.front().dist;
        q.pop();
 
        if (visited[cur] == 1) continue;
        visited[cur] = 1;
 
        for (int i = 0; i < r_list[cur].size(); i++) {
            int next = r_list[cur][i].to;
            int nDist = r_list[cur][i].dist;
 
            if (cDist - nDist == dist[next]) {
                ret++;
                if (visited[next] != 1) {
                    q.push({ next,cDist - nDist });
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        r_list[b].push_back({ a,c });
        cnt[b]++;
    }
 
    cin >> from >> to;
 
    int max = Longest_dist(from);
    int cnt = Find_road(max);
 
    cout << max << endl << cnt;
}