[백준][C++] 1005 ACM Craft

 

 

 

알고리즘 종류

    - 위상 정렬

 

 

 

사고 과정

    - 순서가 있는 정렬이기 때문에 위상 정렬을 떠올렸다.

    - 이전 건물들 A, B의 다음 건물이 C일 때, C의 최종 시간은 아래와 같다.

max(A가 지어지기 까지의 누적 시간 + C가 지어는 시간, B가 지어지기 까지의 누적 시간 + C가 지어지는 시간)

    - 개별 건물이 지어지는 시간을 저장하는 배열 1개가 필요하다.

    - 누적 시간을 기록하는 배열 1개가 필요하다.

 

 

 

구현(C++)

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
int tc;
int n, k;
int target;
 
int inDegree[1001] = {0,}; //진입 차수
int buildTime[1001]; // 개별 건물 건축 시간
int totalBuildTime[1001] = {0,}; // 누적 시간
 
void topology_sort(vector<vector<int> > edge){
    
    queue<int> q;
    
    for(int i=1; i<=n; i++){
        if(inDegree[i] == 0){
            q.push(i);
        }
    }
    
    while(!q.empty()){
        
        int here = q.front();
        q.pop();
        
        if(here == target) return;
        
        for(int i=0; i<edge[here].size(); i++){
            int next = edge[here][i];
            int time = totalBuildTime[here] + buildTime[next];
            
            if(totalBuildTime[next] < time) // 더 큰 누적 시간으로 값 갱신
                totalBuildTime[next] = time;
                
            if(--inDegree[next] == 0){ // 진입 차수가 0인 정점 넣기
                q.push(next);
            }
            
        }
    }
}
 
 
int main(void){
    
    cin >> tc;
    
    while(tc--){
 
        // 초기화
        memset(inDegree, 0, sizeof(inDegree));
        vector<vector<int> > edge;
        edge.resize(1001);
        
        cin >> n >> k;
        
        int delay;
        for(int i=1; i<=n; i++){
            cin >> delay;
            totalBuildTime[i] = delay;
            buildTime[i] = delay;
        }
        
        int a, b;
        for(int i=1; i<=k; i++){
            cin >> a >> b;
            edge[a].push_back(b);
            inDegree[b] += 1;
        }
        
        cin >> target;
        
        topology_sort(edge);
        
        cout << totalBuildTime[target] << endl;
        
    }
    
}

 

 

 

 

시행착오