C++ 코딩테스트 강좌, 임계 경로 구하기

안녕하세요. 이번 강좌에서는 C++ 코딩테스트에서 자주 출제되는 알고리즘 문제 중 하나인 “임계 경로 구하기”에 대해 다루어 보겠습니다. 이 문제는 주로 그래프 이론과 관련된 중요한 개념을 이해하는 데 도움이 됩니다.

문제 정의

주어진 방향 그래프에서 각 정점이 특정 작업을 수행하는 시간을 가지고 있습니다. 임계 경로는 모든 정점을 방문하고, 시작 정점에서 도착 정점으로 가는 경로 중에서 가장 긴 경로의 총 작업 시간을 의미합니다.

문제 설명

그래프의 정점 수 n과 간선 수 m이 주어지고, 각 정점 i에 대해 작업 시간이 t[i]로 주어집니다. 다음과 같은 조건을 만족하는 경로의 작업 시간의 최대값을 구하는 문제입니다.

입력:
n, m
t[0], t[1], ..., t[n-1]
간선: (u1, v1), (u2, v2), ..., (um, vm)
출력:
최대 작업 시간

입력 예시

출력 예시

문제 해결 전략

1. 그래프 표현

우리는 먼저 주어진 정보에 따라 그래프를 인접 리스트 형태로 구성합니다. 이를 통해 각 정점에서 연결된 정점으로의 이동을 쉽게 관리할 수 있습니다.

2. 최장 경로 찾기

DFS(Depth-First Search) 또는 DAG(Directed Acyclic Graph) 성질을 이용해 최장 경로를 구할 수 있습니다. 각 정점을 방문하면서 최장 경로의 최대 작업 시간을 저장해 나가는 방식으로 진행합니다.

3. 동적 프로그래밍(DP) 활용

특히, 임계 경로 구하기 문제는 동적 프로그래밍을 통해 효율적으로 해결할 수 있습니다. 각 정점을 기준으로 도달 가능한 모든 경로의 최대를 누적하여 기록합니다.

C++ 코드 구현

#include 
#include 
#include 
using namespace std;

vector timeTaken; // 각 정점의 작업 시간
vector> graph; // 그래프 인접 리스트
vector dp; // DP 배열

int dfs(int node) {
    if (dp[node] != -1) return dp[node];
    int maxTime = 0;
    for (int next : graph[node]) {
        maxTime = max(maxTime, dfs(next));
    }
    dp[node] = maxTime + timeTaken[node];
    return dp[node];
}

int main() {
    int n, m;
    cin >> n >> m;
    
    timeTaken.resize(n);
    graph.resize(n);
    dp.assign(n, -1);
    
    for (int i = 0; i < n; i++) {
        cin >> timeTaken[i];
    }
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    int result = 0;
    for (int i = 0; i < n; i++) {
        result = max(result, dfs(i));
    }

    cout << result << endl;
    return 0;
}

코드 설명

위 코드는 그래프를 DFS 형태로 탐색하여 임계 경로의 최대 작업 시간을 계산하는 방식입니다. 주요 요소는 다음과 같습니다:

그래프 생성: 입력받은 간선을 통해 인접 리스트 형태로 그래프를 구성합니다.
DFS 함수: 각 정점을 시작으로 연결된 정점들을 재귀적으로 탐색하며 최장 경로의 시간을 계산합니다.
DP 배열: 동일한 정점을 여러 번 방문하지 않도록 DP 배열을 활용하여 메모이제이션 기법을 사용합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n + m)입니다. n은 정점의 수, m은 간선의 수입니다. 최악의 경우 모든 정점을 한 번씩 방문해야 하므로, 이 정도의 복잡도는 일반적으로 효율적입니다.

결론

이번 강좌에서는 C++를 사용하여 임계 경로 구하기 문제를 해결하는 방법에 대해 학습하였습니다. 그래프 이론, 동적 프로그래밍 및 DFS의 개념을 통해 이러한 유형의 문제를 해결할 수 있습니다. 앞으로도 다양한 알고리즘 문제를 연습하여 더 나은 프로그래밍 실력을 갖추시길 바랍니다.