백준 1005 : ACM Craft - 위상정렬, Indegree

전체 소스 코드 (recursion) : https://gitlab.com/greatSumin/cyberbojpractice/blob/master/practice/001_ACM_Craft.cs

전체 소스 코드 (iteration) : https://gitlab.com/greatSumin/cyberbojpractice/blob/master/practice/001_ACM_Craft_indegree.cs

참고한 블로그

recursion : http://deque.tistory.com/8

iteration : http://mygumi.tistory.com/178

후기

recursion 코드는 시간초과가 나와버린 관계로.. iteration 코드만 남겼습니다.

내일 이유를 분석해봐야겠습니다.

위상정렬이란?

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

( 출처 : https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC )

Indegree란?

• 입력 차수(入力次數, 영어: in-degree): 한 꼭짓점으로 들어오는 변의 개수

Indegree를 이용한 위상정렬 알고리즘

<1>

왼쪽의 그림에서 indegree[]는 {0, 1, 1, 2}입니다.

건물의 건설 순서는 cycle일 수 없기 때문에 indegree값이 0인 건물은 무조건 존재함을 알 수 있습니다.

이제부터 indegree값이 0인 건물만 차근차근 계산해주면 됩니다.

<2>

A건물을 지어야만 B건물을 지을 수 있을 때

B를 A의 목표건물이라 하겠습니다.

indegree 값이 0인 1번 건물의 목표건물인 B와 A에 대해서 건설시간을 계산합니다.

기존의 건설시간에 1번 건물의 건설시간을 더한 값을 갖게 됩니다.

이때 2, 3번 건물은은 indegree값이 1씩 줄어들어 0이 됩니다.

<3>

같은 과정을 거쳐 2,3번 건물을 계산하면 4번 건물의 최소 건설시간을 구할 수 있습니다.

CODE 하이라이트

for(int t = 0;t<test_case;t++) {
    // 변수 설명
    /*
        int build_num : 건물의 개수
        int rule_num : 건설 규칙의 개수
        int goal : 지어야하는 건물

        int[] memo : 각 건물당 최소 건설시간. 고로 memo[goal - 1]이 우리가 찾는 정답
        int[] build_time : 건설시간
        bool[,] connection : i를 지어야만 j를 지을 수 있다면 connection[i,j]==true
        int[] indegree : 각 건물에서 자신에게 들어오는 방향인 간선의 개수
    */            
    Queue<int> q = new Queue<int>(); // indegree값이 0인 건물들을 저장하는 Queue
    for(int i = 0;i<build_num;i++) {
        if(indegree[i]==0)
            q.Enqueue(i);
    }
        
    while(q.Count != 0) { // 더 이상 indegree값이 0인 건물이 없을 때까지 loop
        int v = q.Dequeue();
        for(int i = 0;i<build_num;i++)
            if(connection[v, i]) {
                memo[i] = Math.Max(memo[i], memo[v] + build_time[i]);
                if(--indegree[i]==0) // 해당 간선은 계산을 마쳤으니 제외
                    q.Enqueue(i);
            }
    }
                
    result[t] = memo[goal - 1];
}