임계경로( BOJ 1948 )

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

1948번: 임계경로

 

문제 파악하기

임계경로의 길이 및 임계경로에 해당하는 간선의 개수를 구하는 문제입니다. 월드 나라를 그래프로 직접 표현해보면 시작과 종료 정점이 정해져있으며, 싸이클이 없는 그래프로 그려지기 때문에 손쉽게 임계 경로를 구하는 문제라는 걸 눈치챌 수 있습니다. 다만, 임계 경로에 해당하는 간선의 개수를 세기 위해서는 약간의 알고리즘이 필요합니다.

 

문제 해결하기

우선, 임계경로의 길이를 구해봅시다. 위상 정렬 알고리즘을 활용하면 전체적인 임계경로의 길이를 구할 수 있습니다. 위상 정렬 알고리즘을 간단하게 말하자면 그래프를 왼쪽에서 오른쪽으로 나아가는 방향으로 그린다고 가정했을 때, 가장 왼쪽에 위치한 정점부터 탐색을 시작하는 알고리즘입니다. 여기서 말하는 가장 왼쪽이란 해당 정점으로 들어오는 간선이 없는 정점을 의미합니다. 이렇게 가장 왼쪽부터 순서대로 탐색하고, 이미 확인한 간선을 하나씩 지워주면 결국 가장 오른쪽에 위치한 정점까지 탐색하면서 임계 경로의 길이를 구할 수 있습니다. 이렇게 임계경로의 길이를 구하면 다음으로 각각의 간선이 임계경로에 포함되는지 확인해봅시다.

 

간선을 확인하기 위해서는 도착 지점부터 탐색을 시작해야 합니다. 스택을 사용하여 간선을 역순으로 확인하면서 모든 간선을 하나씩 확인해보면 됩니다. 만약, 현재 간선의 비용만큼 연결된 두 정점의 임계경로 길이가 증가했다면 임계경로입니다. 하지만 현재 간선의 시작 정점에서 간선의 비용만큼 더한 값보다 도착 지점의 임계경로 길이가 더 길다면 현재 간선은 임계경로가 아닙니다. 이렇게 하나씩 경로를 확인해보면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define NMAX 10010
#define PAIR pair<int, int>
using namespace std;
 
int N, M, s, e, c;
vector< PAIR > adj[NMAX];
 
int cur, ccst, nxt, ncst;
int enter[NMAX], cst[NMAX], check[NMAX];
queue< int > q;
 
int cnt;
stack< pair< int, PAIR > > edges;
 
int main() {
    // 입력
    scanf("%d", &N);
    scanf("%d", &M);
    for(int i=1;i<=M;i++) {
        scanf("%d %d %d", &s, &e, &c);
        
        adj[s].push_back({e, c});
        enter[e]++;
    }
    scanf("%d %d", &s, &e);
    
    // 위상정렬
    q.push(s);
    while(!q.empty()) {
        cur = q.front();
        q.pop();
        
        if(cur == e) continue;
        
        for(PAIR edge:adj[cur]) {
            nxt = edge.first;
            ncst = cst[cur] + edge.second;
            
            cst[nxt] = max( cst[nxt], ncst );
            
            enter[nxt]--;
            if(!enter[nxt]) q.push(nxt);
            
            edges.push({cur, edge});
        }
    }
    
    // 처리한 간선 역순으로
    check[e] = 1;
    while(!edges.empty()) {
        cur = edges.top().first;
        nxt = edges.top().second.first;
        ccst = edges.top().second.second;
        
        edges.pop();
        
        // 임계 경로
        if(check[nxt] and cst[cur] + ccst == cst[nxt]) {
            check[cur] = 1;
            cnt++;
        }
    }
    
    // 출력
    printf("%d\n", cst[e]);
    printf("%d", cnt);
}
 

후기

문제에서 그래프에 대한 설명을 이해하는데 시간이 조금 걸렸던 문제입니다. 하지만 임계경로에 포함된 간선의 개수를 파악하는 알고리즘을 만드는 건 나름 재미있던 문제입니다. 위상정렬을 활용하는 사람에게 추천하는 문제입니다.