[위상정렬] 백준 작업 2056번 with Python3 ★★★

 

https://www.acmicpc.net/problem/2056

2056번: 작업

 

문제

정답 풀이

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]))  # 각 작업번호i에 걸리는 시간 time[i]
    print(q)
    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]:
                # index = 후작업 번호/ i =선행작업 번호

                # 사용한 연결점은 삭제 /
                indegree[i].remove(index)

                # 현재 index에 필요한 선행 작업 i중 가장 오래 걸리는 선행작업 값을, index작업 시간과 더해서 temp[i]에 담는다.
                temp[i] = max(temp[i], cost + time[i])

                # 진입 차수가 0인 것들은 cost를 temp[i] 해서 q에 넣고 위상정렬을 계속한다.
                if len(indegree[i]) == 0:
                    q.append((i, temp[i]))

                    # 가장 큰 경우의 수를 total에 담는다.
                    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)
            # 진입하는 방향이 indegree에 들어간다.
            # indegree index = 선행작업 / 원소 = 후 작업

    print(time)
    print(indegree)
    answer = topological()
    print(answer)

출처:https://jjangsungwon.tistory.com/127

 

해석

문제 풀이 중에서 대부분은 defaultdict 이라는 함수를 사용했는데 이것은 사용하지 않은 위상정렬이었다.

 

개인적으로 이 문제가 장난감 만들기 문제보다 이해하기 어려웠던것 같다. 

 

위상정렬이라는 개념을 아직 어떻게 해야 능숙하게 활용할 수 있을지 모르겠다.

 

장난감 만들기와의 차이점은 장난감은 낮은 번호에서부터 올라갔다면, 여기선 높은 번호부터 아래로 내려가면서 탐색을 한다. 이는 선행작업이 여러개일 경우 그 중에서 가장 오래 걸리는 것을 저장해야하기 때문.