본 강좌에서는 임계 경로 문제를 해결하기 위한 알고리즘에 대해 알아보겠습니다. 임계 경로(Critical Path)는 프로젝트 관리에서 각 작업의 시작 및 완료 시점을 보여주는 것으로, 전체 프로젝트를 완료하는 데 가장 길게 걸리는 경로를 의미합니다. 엔지니어링 및 소프트웨어 프로젝트에서 매우 중요한 개념이며, 실제 코딩 테스트에서도 자주 출제되는 주제 중 하나입니다.
문제 정의
다음과 같은 구조의 방향 그래프가 주어질 때, 임계 경로를 구하는 문제를 다루고자 합니다. 그래프의 각 노드는 작업을 의미하며, 엣스는 작업 간의 선후 관계를 의미합니다. 우리가 구해야 할 것은 전체 작업을 완료하기 위한 최소 소요 시간을 계산하는 것입니다.
문제 설명
입력: - n (1 ≤ n ≤ 100): 작업의 수 - edges: 각 작업 간의 의존 관계를 나타내는 리스트로, 각 요소는 튜플 (u, v, w)로 이루어져 있으며, 여기서 u는 작업의 시작 노드, v는 작업의 끝 노드, w는 작업을 완료하는데 필요한 시간 출력: - 전체 작업을 완료하는데 걸리는 가장 긴 시간 (임계 경로의 길이)
예제 입력
n = 5
edges = [
(1, 2, 3),
(1, 3, 2),
(2, 4, 4),
(3, 4, 5),
(4, 5, 1)
]
예제 출력
8
문제 풀이 및 접근 방법
이 문제를 해결하기 위해서는 다음과 같은 단계를 따라서 구현할 수 있습니다.
1. 방향 그래프 표현
우선 입력 받은 엣지 정보를 바탕으로 그래프를 구조화해야 합니다. 이를 위해, 인접 리스트 형태로 그래프를 구성하겠습니다. 또한 각 작업의 완료 시간을 저장하기 위한 배열을 준비합니다.
from collections import defaultdict
import sys
def critical_path(n, edges):
graph = defaultdict(list)
in_degree = [0] * (n + 1)
completion_time = [0] * (n + 1)
# 그래프 구성 및 진입 차수 계산
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
2. 위상 정렬
다음 단계는 그래프의 위상 정렬을 수행하여 모든 작업을 안전하게 처리할 수 있도록 하는 것입니다. 위상 정렬을 통해 각 작업이 완료되는 순서를 정할 수 있으며, 작업의 의존성을 고려해야 합니다.
# 위상 정렬 수행
zero_degree_queue = []
for i in range(1, n + 1):
if in_degree[i] == 0:
zero_degree_queue.append(i)
topo_order = []
while zero_degree_queue:
node = zero_degree_queue.pop(0)
topo_order.append(node)
for neighbor, duration in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
zero_degree_queue.append(neighbor)
3. 최소 소요 시간 계산
이제 위상 정렬된 순서대로 각 작업의 완료 시간을 계산합니다. 각 작업을 수행할 때마다, 해당 작업에 연결된 모든 노드의 완료 시간을 갱신하게 됩니다. 이를 통해 각 작업까지의 소요 시간을 저장할 수 있습니다.
for node in topo_order:
for neighbor, duration in graph[node]:
completion_time[neighbor] = max(completion_time[neighbor], completion_time[node] + duration)
# 전체 작업 완료하는데 걸리는 최대 시간
return max(completion_time)
4. 전체 코드 작성
모든 단계를 통합하여 최종 코드를 작성하겠습니다.
def critical_path(n, edges):
graph = defaultdict(list)
in_degree = [0] * (n + 1)
completion_time = [0] * (n + 1)
# 그래프 구성 및 진입 차수 계산
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# 위상 정렬 수행
zero_degree_queue = []
for i in range(1, n + 1):
if in_degree[i] == 0:
zero_degree_queue.append(i)
topo_order = []
while zero_degree_queue:
node = zero_degree_queue.pop(0)
topo_order.append(node)
for neighbor, duration in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
zero_degree_queue.append(neighbor)
# 각 작업의 완료 시간 계산
for node in topo_order:
for neighbor, duration in graph[node]:
completion_time[neighbor] = max(completion_time[neighbor], completion_time[node] + duration)
# 전체 작업 완료하는데 걸리는 최대 시간
return max(completion_time)
# 예제 실행
if __name__ == "__main__":
n = 5
edges = [
(1, 2, 3),
(1, 3, 2),
(2, 4, 4),
(3, 4, 5),
(4, 5, 1)
]
result = critical_path(n, edges)
print("임계 경로의 길이:", result)
결론
이번 강좌에서는 임계 경로를 구하는 방법에 대해 알아보았습니다. 그래프 이론과 위상 정렬을 통해 각각의 작업을 안전하게 처리하고, 각 작업의 소요 시간을 계산하여 임계 경로를 도출하는 방식으로 문제를 해결했습니다. 이러한 접근법은 결과적으로 다양한 프로젝트 관리 및 스케줄링 문제에 적용될 수 있습니다.
더불어 실무에서도 이러한 알고리즘은 복잡한 프로젝트 관리의 기초로, 효율성을 높이는 데에 큰 도움을 줄 것입니다. 앞으로도 다양한 알고리즘 문제를 다루면서 프로그래밍 실력을 키워나가길 바랍니다.