[BOJ 1948 // C++] 임계경로

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1948번 문제인 임계경로이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1948

1948번: 임계경로

글쓴이는 이 문제를 위상정렬(topological sorting)으로 도착도시까지 찾아가면서 각 도시까지 걸리는 최대시간으로 가는 경로가 되는 도시들을 저장한 후, 도착도시에서 출발도시방향으로 역추적하며 간선의 수를 세어 풀었다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;
using std::pair;

vector<pair<int,int>> G[10001]; // 출발도시에서 도착도시로 가는 가중치 있는 그래프
int inway[10001]; // i번 노드로 들어오는 경로수(indegree)
int dist[10001]; // i번 노드까지 오는 데에 걸리는 최대 시간
vector<int> cnt[10001]; // i번 노드로 들어오는 데에 최대 시간이 걸리는 경로인 이전노드들을 모은 그래프
int target; // 도착도시
bool visited[10001]; // backtrack에서 이미 확인한 도시 중복탐색 방지용
int running = 0; // 달려야하는 도로 수

void backtrack(int node) {
    vector<int>::iterator iter = cnt[node].begin();
    for (;iter != cnt[node].end();iter++) {
        running++;
        if (!visited[*iter]) {
            visited[*iter] = 1;
            backtrack(*iter);
        }
    }
}

void dfs(int root, int parent) {
    if (root == target) {
        backtrack(target);
        cout << dist[target] << '\n' << running;
    }
    vector<pair<int, int>>::iterator iter = G[root].begin();
    for (;iter != G[root].end();iter++) {
        int current = (*iter).first, l = (*iter).second;
        inway[current]--;
        if (dist[current] < dist[root] + l) {
            dist[current] = dist[root] + l;
            cnt[current].clear();
            cnt[current].push_back(root);
        }
        else if (dist[current] == dist[root] + l) {
            cnt[current].push_back(root);
        }
        if (inway[current] == 0) dfs(current, root);
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for (int i = 0;i < m;i++) {
        int s, e, t; cin >> s >> e >> t;
        G[s].push_back({e,t});
        inway[e]++;
    }
    
    int root;
    cin >> root >> target;
    dfs(root, 0);

    return 0;
}