[C/C++] 백준 #2056 작업(위상정렬)

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

2056번: 작업

 

이번 문제는 선행작업과 후행작업이 있을 때, 전체 작업시간이 얼마나 걸릴 것인지 판단하는 것입니다.  소프트웨어 공학에서 자주 발생하는 일입니다.  소프트웨어 공학에서도 선행작업과 후행작업이 있는 경우 작업 인력을 무한정 투입할 경우 마칠 수 있는 최소 시간을 구하게 됩니다.  

 

이와 같이 작업의 선후가 있는 경우에 위상정렬을 사용하게 됩니다.  위상절렬은 작업의 선후에 따라서 정렬을 하는 것이지만, 이 문제에서는 작업시간을 최종적으로 결정해야 합니다.  위상정렬과 이 문제는 크게 다르지 않습니다.  단지 작업시간을 후행작업에게 알려주는 추가 작업만 더 해주시면 됩니다.

 

위상정렬을 이용하는 문제들입니다.

https://sdev.tistory.com/894

[C/C++] 백준 #1766 문제집(위상정렬)

 

https://sdev.tistory.com/682

#1516 게임 개발

 

https://sdev.tistory.com/597

#79 암호 알아내기(Topology Sort)

 

위상정렬(Topological Sort)은 이름과는 달리 구현 방법이 간단한 알고리즘입니다.

 

Topological Sort

 

위상 정렬은 선후 관계를 나타내는 방향 그래프(DAG)로 구성되어 있습니다.  인입간선은 해당 작업의 선행 작업이 있다는 의미이고, 진출간선은 후행 작업이 있다는 의미입니다.  인입간선이 하나도 없다는 것은 해당 작업은 지금 바로 실행할 수 있다는 의미를 가집니다.  그래서 인입간선이 하나도 없는 노드들을 이용해서 해당 노드의 진출간선을 제거하면서 알고리즘이 반복되면 됩니다.

 

다음은 제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2056 - Job
//        - by Aubrey Choi
//        - created at 2019-07-18
//------------------------------------------------
#include <stdio.h>

struct Node { int s, value, count; int link[100]; };

int main()
{
    int n, max = 0, i, j, m;
    static Node node[10001];
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d%d", &node[i].value,&node[i].count);
        for(j=0; j<node[i].count; j++) scanf("%d", &node[i].link[j]);
    }
    for(i = 1; i <= n; i++)
    {
        for(j=0, m=0; j<node[i].count; j++)
        {
            int f = node[i].link[j];
            if(node[f].s > m) m = node[f].s;
        }
        node[i].s = m + node[i].value;
        if(node[i].s > max) max = node[i].s;
    }
    printf("%d\n", max);
}