자바스크립트 코딩테스트 강좌, 임계 경로 구하기

문제 설명

여러분은 다양한 작업이 연결되어 있는 프로젝트 관리 시스템을 관리하고 있습니다. 각 작업은 특정 시간 동안 수행되어야 하며, 어떤 작업은 다른 작업의 완료 후에만 시작할 수 있습니다. 이러한 관계를 파악하고, 프로젝트가 완료되는 데 필요한 최소 시간을 계산하는 알고리즘을 구현하세요.

프로젝트는 다음과 같은 정보로 구성됩니다:

n : 작업의 개수
dependencies : 각 작업 간의 종속 관계를 나타내는 배열
times : 각 작업을 수행하는 데 필요한 시간의 배열

함수의 형식은 다음과 같습니다:

function criticalPath(n, dependencies, times) {
    // 여기에 코드를 작성하세요.
}

입력 예시

n = 5
dependencies = [[1, 0], [2, 1], [3, 1], [3, 2], [4, 3]]
times = [3, 2, 5, 1, 2]
입력: criticalPath(n, dependencies, times)

출력 예시

출력: 11

문제 풀이 접근법

이 문제를 해결하기 위해서는 다음과 같은 단계를 거쳐야 합니다:

1. 그래프 모델링

작업과 그 간의 종속 관계를 그래프 형태로 변환하여 표현합니다. 각 작업을 정점으로, 종속 관계를 간선으로 표현할 수 있습니다.

2. 위상 정렬 (Topological Sort)

주어진 그래프의 위상 정렬을 통해 작업의 수행 순서를 정합니다. 위상 정렬은 방향 그래프의 모든 정점을 방문하는 선형 배열을 찾는 과정입니다.

3. 최장 경로 (Longest Path) 계산

위상 정렬을 이용하여 각 작업의 시작 시점을 계산하고, 최종적으로 모든 작업이 완료되는 데 걸리는 최소 시간을 구합니다.

구현 코드

다음은 위의 접근법을 구현한 자바스크립트 코드입니다:

function criticalPath(n, dependencies, times) {
    const adjList = Array.from({length: n}, () => []);
    const inDegree = Array(n).fill(0);
    
    // 1. 그래프와 진입 차수 계산
    for (const [next, prev] of dependencies) {
        adjList[prev].push(next);
        inDegree[next]++;
    }
    
    // 2. 위상 정렬을 위한 큐 생성
    const queue = [];
    const timeToComplete = Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        timeToComplete[i] = times[i];
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    // 3. 최장 경로 계산
    let maxTime = 0;

    while (queue.length) {
        const current = queue.shift();
        maxTime = Math.max(maxTime, timeToComplete[current]);

        for (const neighbor of adjList[current]) {
            timeToComplete[neighbor] = Math.max(timeToComplete[neighbor], timeToComplete[current] + times[neighbor]);
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    return maxTime;
}

코드 설명

이제 각 코드의 부분을 살펴보겠습니다:

1. 그래프 구성 및 진입 차수 계산

우선 입력으로 주어진 작업의 종속 관계를 기반으로 인접 리스트를 생성하고, 각 정점의 진입 차수를 계산합니다. 진입 차수가 0인 작업은 바로 시작할 수 있는 작업이므로 큐에 추가합니다.

2. 위상 정렬 및 최장 경로 계산

큐에서 작업을 하나씩 꺼내어 그 작업에 연결된 후속 작업들의 최장 완료 시간을 업데이트합니다. 만약 후속 작업의 진입 차수가 0이 된다면 다시 큐에 추가합니다. 모든 작업을 처리한 후 가장 긴 시간을 기록하면 그게 임계 경로입니다.

시간 복잡도 분석

이 알고리즘은 그래프의 정점과 간선을 각각 한 번씩 탐색하므로 시간 복잡도는 O(V + E) 입니다. 여기서 V는 작업의 개수, E는 작업 간의 종속 관계의 개수입니다.

최종 생각

임계 경로를 구하는 문제는 프로젝트 관리 및 일정 계획에서 중요한 요소로, 실제 산업에서도 많이 사용됩니다. 이 문제를 통해 그래프와 위상 정렬의 개념을 이해하고, 자바스크립트로 복잡한 문제를 해결하는 능력을 키울 수 있습니다.

추가 연습 문제

이제 여러분의 실력을 테스트하기 위해 다음과 같은 문제들을 연습해보세요:

작업 간의 종속 관계가 다를 때, 임계 경로의 변경을 추적하는 알고리즘을 구현하십시오.
작업의 시간뿐만 아니라 비용을 고려하여 최적의 경로를 찾는 문제가 있다. 이 문제를 해결하기 위한 접근법은 무엇인가요?
그래프가 다른 구조를 가질 때(예: 비순환 방향 그래프) 위상 정렬을 어떻게 응용할 수 있을까요?

참고 자료

임계 경로 문제를 더 자세히 알고 싶다면 아래 링크를 참고하세요: