[백준 2056] 작업 - Python

문제 보기

 

[사용한 알고리즘]

위상 정렬(Topological)

 

[알고리즘]

1. 선행 관계가 없는 작업을 큐에 삽입합니다.

2. 큐에 있는 원소를 하나씩 꺼내어 연결된 선행 관계를 제거합니다.

 - 선행 관계를 제거한 결과 해당 작업이 더 이상 선행 관계가 없으면 큐에 삽입합니다.

 - 최대 시간 저장 배열에 저장된 시간과 현재까지 사용한 시간 중 최댓값을 저장합니다.

3. 모든 선행 관계가 사라질 때까지 위 과정을 반복합니다.

 

※ 최대 시간 저장 배열을 따로 두는 이유

예를 들어 3번 작업이 1번, 2번 작업과 선행 관계가 있을 때 1번 + 3번, 1번 + 2번 작업 중 최댓값이 3번 작업 처리 시간입니다. 만약 최대 시간 저장 배열을 따로 두지 않으면 가장 마지막에 계산한 값이 최종 시간이 되기 때문에 따로 시간을 관리하는 배열이 필요합니다.

 

[코드]

import sys
from collections import deque


def topological():
    q = deque()
    # 진입 차수가 0인 값 q에 삽입
    for i in range(1, n + 1):
        if len(indegree[i]) == 0:
            q.append((i, time[i]))

    total = 0
    temp = [0] * (n + 1)
    temp[1] = time[1]

    # 위상 정렬
    while q:
        index, cost = q.popleft()
        total = max(total, cost)
        # index와 연결된 부분 처리
        for i in range(1, n + 1):
            if index in indegree[i]:
                indegree[i].remove(index)
                temp[i] = max(temp[i], cost + time[i])
                if len(indegree[i]) == 0:
                    q.append((i, temp[i]))
                    total = max(total, temp[i])
    return total


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    indegree = [[] for _ in range(n + 1)]
    time = [0] * (n + 1)  # 작업 시간
    for i in range(n):
        array = list(map(int, input().split()))
        time[i + 1] = array[0]
        for j in range(array[1]):
            indegree[array[2 + j]].append(i + 1)

    answer = topological()
    print(answer)