[백준/Baekjoon] 1948 임계경로 C++ :: BFS & Topological sort

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

1948번: 임계경로

---

1. Logic

우리가 이 문제에서 구해야 할 점은 2가지이다.

1. 모든 사람들이 만나는 시간.

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

 

이제 구하는 로직을 설명해 볼건데 순서대로 보면

1. 모든 사람들이 만나는 시간.

모든 사람들이 만나려면 도착점에 먼저 들어온 사람은 가장 늦게 도착한 사람이 올 때 까지 기다려야 한다. 그렇기 때문에 모든 사람들이 만나는 시간이 뜻하는 바는 출발지점에서 도착지점까지 가장 오래 걸리는 경로의 값이다.

 

이 부분 문제에 대해 위상정렬로 해결할 수 있는데 출발도시로 가려면 시작도시에서 출발도시로 이어진 도시를 거쳐야만 도착할 수 있기 대문에 위상 정렬을 이용하여 최대 비용을 구하면 된다.

 

2. 쉬지 않고 달려야하는 사람들이 지나는 도로의 수

도착지점에서 출발지점까지 반대로 역으로 BFS를 돌면서 최대 임계 경로를 구하고 지나온 도로의 갯수를 세주면 된다.

이 부분은 트리의 지름 문제를 풀어보면 이해가 쉬울 것 같다.

이 부분에 대해서 나도 문제를 풀고 블로그를 작성해 논 글이 있으니 빠르게 이해하고싶다면 참고해도 또한 좋을 것 같다.

https://go2gym365.tistory.com/103

[백준/Baekjoon] 1167 트리의 지름 C++ :: Graph & DFS

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;
int s, e;
int cnt = 0;
int inDegree[10001];
int dist[10001];
bool vis[10001];
vector<pair<int, int>> graph[10001];
vector<pair<int, int>> revGraph[10001];

void topologicalSort() {
    queue<pair<int, int>> q;
    q.push({s, 0});

    while(!q.empty()) {
        int cur = q.front().first;
        int curCost = q.front().second;
        q.pop();

        for(int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i].first;
            int nCost = graph[cur][i].second;

            dist[next] = max(dist[next], curCost + nCost);
            inDegree[next]--;

            if(!inDegree[next]) q.push({next, dist[next]});
        }
    }
}

void revBFS() {
    queue<int> q;
    q.push(e);
    vis[e] = true;

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        for(int i = 0; i < revGraph[cur].size(); i++) {
            int next = revGraph[cur][i].first;
            int ncost = revGraph[cur][i].second;

            if(dist[cur] - ncost == dist[next]) {
                cnt++;
                if(!vis[next]) {
                    vis[next] = true;
                    q.push(next);
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        revGraph[b].push_back({a, c});
        inDegree[b]++;
    }

    cin >> s >> e;

    topologicalSort();
    revBFS();

    cout << dist[e] << "\n" << cnt;
}

---

3. Feedback

골드 상위부터는 이제 아이디어도 같이 필요한 것 같다. 아이디어를 떠올린 후 알고리즘을 접목시키는데 초점을 두고 로직을 생각해 봐야 겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐