[백준문제풀이] 1948 임계경로

 

풀이일시 : 2020-08-19

​

 

문제 :

월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.

이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.

어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라.

출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

​

 

입력:

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

그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.

모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.

ex)

7

9

1 2 4 // 출발도시 1 도착도시 2 걸리는시간 4

1 3 2

1 4 3

2 6 3

2 7 5

3 5 1

4 6 4

5 6 2

6 7 5

1 7

​

 

출력:

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

ex)

12

5

​

 

풀이 :

모든 임계경로를 구해야 해서 역추적을 사용해야한다.

 

#include <iostream>
#include <queue>
#include <vector>
#define MAX 10001

using namespace std;

class Edge {
public:
    int node;
    int time;
    Edge(int node, int time) { //생성자로 초기화
        this->node = node;
        this->time = time;
    }
};

int n, start, finish;
int inDegree[MAX], result[MAX], c[MAX]; //result : 이들이 만나는 시간
vector<Edge> a[MAX];
vector<Edge> b[MAX];

void topologySort() {
    queue<int> q;
    q.push(start); //처음 있는거를 큐에 넣는다. (진입차수0이라그랬음)
    while (!q.empty()) { //큐가 빌때까지 계속한다.
        int x = q.front(); //큐의 맨앞에있는게 x
        q.pop();
        for (int i = 0; i < a[x].size(); i++) { //인접노드를 번갈아가며
            Edge y = Edge(a[x][i].node, a[x][i].time); //y에는 마지막노드뿐 아니라 시간도 같이저장
            if (result[y.node] <= y.time + result[x]) {//시간이 time을 더한것보다 작으면
                result[y.node] = y.time + result[x]; //더 큰값으로 갱신해준다.
            }
            if (--inDegree[y.node] == 0) //새롭게 진입차수가 0이 된것이 있다면
                q.push(y.node); //큐에 삽입해준다.
        }
    }


    //결과를 역추적한다.
    int count = 0;
    q.push(finish); //끝에있는걸 큐에 넣는다.
    while (!q.empty()) { //큐가빌때까지 반복
        int y = q.front();
        q.pop(); //꺼내준다
        for (int i = 0; i < b[y].size(); i++) { //노드의 갯수만큼 반복
            Edge x = Edge(b[y][i].node, b[y][i].time); 
            //도착점에 연결되어있는 시작점을 하나씩 확인하면서 최장경로인지 확인
            if (result[y] - result[x.node] == x.time) { //최장경로의 조건
                count++; //최장경로의 갯수를 증가시켜준다.
                //큐에는 한 번씩만 담아 추적한다.
                if (c[x.node] == 0) {
                    q.push(x.node);
                    c[x.node] = 1;
                }
            }
        }
    }
    printf("%d\n%d", result[finish], count); //count : 1분도 쉬지 않고 달려야 하는 도로의 수
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, node, time;
        cin >> x >> node >> time; //출발, 도착, 걸리는시간
        a[x].push_back(Edge(node, time)); //출발, (도착, 걸리는시간)
        b[node].push_back(Edge(x, time)); //도착, (출발, 걸리는시간)
        inDegree[node]++; //node의 진입차수 ++
    }
    //1 7 이면 7로가는 경로를 찾는데, 가장 오래걸리는 시간을 찾아야된다.
    //가장 오래걸리는 시간을 찾고 그를 지나는 노드들이 바로 쉬지않고 달려야되는 도로의 수이다.
    cin >> start >> finish; 
    topologySort();
}