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

서론

소프트웨어 개발과 관련된 많은 기업에서 코딩 테스트는 필수적인 채용 과정으로 자리 잡고 있습니다.
특히, 자바는 많은 기업에서 선호되는 프로그래밍 언어 중 하나입니다.
이번 포스트에서는 자바를 사용하여 ‘임계 경로 구하기’ 문제를 해결하는 방법에 대해 자세히 알아보겠습니다.
임계 경로는 유 directed graph에서 가장 긴 경로를 찾는 것을 의미하며, 특히 프로젝트 관리 도구에서 일정 계획을 세우는 데 중요한 역할을 합니다.

문제 설명

주어진 방향 그래프에서 각 노드는 작업을 의미하고, 각 간선은 작업 간의 의존성을 나타냅니다.
여기서 방향 그래프의 노드를 시작으로 하여 최종 노드까지 도달하는 가장 긴 경로를 찾는 것이 우리의 목표입니다.
예를 들어, 각 작업의 수행 시간도 주어졌을 때, 프로젝트 완료까지 걸리는 최대 시간을 구하라는 것이 문제의 요지입니다.

입력 형식

정수 N: 작업의 개수 (1 ≤ N ≤ 10,000)
정수 M: 의존성의 개수 (1 ≤ M ≤ 100,000)
각 작업의 수행 시간: 배열의 형태로 주어짐
의존성 정보: 배열의 형태로 주어짐 (a → b: 작업 a는 작업 b가 완료된 후에 수행 가능)

출력 형식

최종 작업을 완료하는 데 걸리는 최대 시간을 출력합니다.

예제

        **입력**:
        5 4
        [2, 3, 4, 1, 5]
        [
            (0, 1),
            (1, 2),
            (1, 3),
            (3, 4)
        ]
        
        **출력**:
        10

이 예제에서는 최대 경로가 2(0에서 1로) + 3(1에서 2로) + 5(3에서 4로)로 None의 연속성을 위한 것을 기반으로 한다면 최종 작업을 완료하는 데 10의 시간이 소요됩니다.

문제 접근 방법

‘임계 경로 구하기’ 문제를 해결하기 위해서는 그래프 탐색 알고리즘을 활용할 수 있습니다.
일반적으로 Topological Sort을 사용하여 작업의 순서를 정한 후, 각 노드에 대해 누적 시간을 계산하여 최종 시간을 결정하게 됩니다.
전체적인 풀이는 다음과 같은 단계로 진행됩니다:

그래프 생성: 각 작업과 그 작업에 의존적인 작업을 연결하는 방향 그래프를 생성합니다.
탑오로지 정렬: 의존성이 있는 작업을 정렬하여 순서대로 작업을 수행할 수 있도록 합니다.
시간 계산: 각 작업을 수행하는 데 걸리는 시간을 누적하여 최종 목표 작업의 시간을 계산합니다.

1단계: 그래프 생성

입력된 의존성 정보를 사용하여 그래프를 생성합니다.
각 작업을 정점으로 보고, 의존성에 대해 간선으로 연결합니다.
자바에서는 ArrayList를 사용하여 그래프를 표현할 수 있습니다.

        List> graph = new ArrayList<>();
        int[] indegree = new int[N];
        int[] time = new int[N];

        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }

        // 의존성 정보를 기반으로 그래프 구성
        // (a, b)를 통해 a → b로 간선 추가
        for (int[] dep : dependencies) {
            graph.get(dep[0]).add(dep[1]);
            indegree[dep[1]]++;
            time[dep[0]] = taskTimes[dep[0]];
        }

2단계: 탑오로지 정렬

그래프가 만들어지면, 차수(indegree)가 0인 노드부터 시작하여 위상 정렬을 통해 정점을 탐색합니다.
주로 큐를 사용하여 구현할 수 있습니다.

        Queue queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] dp = new int[N]; // 각 작업 완료 시간 저장
        while (!queue.isEmpty()) {
            int u = queue.poll();
            dp[u] = Math.max(dp[u], time[u]);

            for (int v : graph.get(u)) {
                indegree[v]--;
                dp[v] = Math.max(dp[v], dp[u] + time[v]);
                if (indegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

3단계: 시간 계산

마지막 작업까지 도달했을 때, dp 배열의 최댓값이 바로 프로젝트 완료에 걸리는 최대 시간을 나타냅니다.

        int result = 0;
        for (int t : dp) {
            result = Math.max(result, t);
        }
        System.out.println(result);

자바 코드

        import java.util.*;

        public class CriticalPath {
            public static void main(String[] args) {
                // 입력 처리
                Scanner sc = new Scanner(System.in);
                int N = sc.nextInt();
                int M = sc.nextInt();
                int[] taskTimes = new int[N];
                for (int i = 0; i < N; i++) {
                    taskTimes[i] = sc.nextInt();
                }
                List> graph = new ArrayList<>();
                int[] indegree = new int[N];

                for (int i = 0; i < N; i++) {
                    graph.add(new ArrayList<>());
                }

                for (int i = 0; i < M; i++) {
                    int a = sc.nextInt();
                    int b = sc.nextInt();
                    graph.get(a).add(b);
                    indegree[b]++;
                }

                // 위상 정렬 및 시간 계산
                Queue queue = new LinkedList<>();
                for (int i = 0; i < N; i++) {
                    if (indegree[i] == 0) {
                        queue.offer(i);
                    }
                }

                int[] dp = new int[N];
                while (!queue.isEmpty()) {
                    int u = queue.poll();
                    dp[u] = Math.max(dp[u], taskTimes[u]);

                    for (int v : graph.get(u)) {
                        indegree[v]--;
                        dp[v] = Math.max(dp[v], dp[u] + taskTimes[v]);
                        if (indegree[v] == 0) {
                            queue.offer(v);
                        }
                    }
                }

                // 최대 시간 계산
                int result = Arrays.stream(dp).max().getAsInt();
                System.out.println(result);
            }
        }

결론

이번 강좌에서는 자바를 이용한 임계 경로 구하기 문제를 해결하는 과정을 다뤘습니다.
그래프 이론을 활용하여 각 작업의 의존성을 나타내고, 최종 작업의 완료 시간을 계산하는 방법을 배웠습니다.
이처럼 알고리즘 문제를 해결하는 과정에서 단계적인 접근이 중요하며, 이를 통해 실제 코딩 테스트에서도 좋은 성과를 낼 수 있습니다.
앞으로도 다양한 알고리즘을 다루는 글을 지속적으로 작성할 예정이니 많은 관심 부탁드립니다.

서론