서론
소프트웨어 개발과 관련된 많은 기업에서 코딩 테스트는 필수적인 채용 과정으로 자리 잡고 있습니다.
특히, 자바는 많은 기업에서 선호되는 프로그래밍 언어 중 하나입니다.
이번 포스트에서는 자바를 사용하여 ‘임계 경로 구하기’ 문제를 해결하는 방법에 대해 자세히 알아보겠습니다.
임계 경로는 유 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);
}
}
결론
이번 강좌에서는 자바를 이용한 임계 경로 구하기 문제를 해결하는 과정을 다뤘습니다.
그래프 이론을 활용하여 각 작업의 의존성을 나타내고, 최종 작업의 완료 시간을 계산하는 방법을 배웠습니다.
이처럼 알고리즘 문제를 해결하는 과정에서 단계적인 접근이 중요하며, 이를 통해 실제 코딩 테스트에서도 좋은 성과를 낼 수 있습니다.
앞으로도 다양한 알고리즘을 다루는 글을 지속적으로 작성할 예정이니 많은 관심 부탁드립니다.