[BOJ] 1005번 : ACM craft

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

1005번: ACM Craft

 

오랜만에 그래프 문제를 풀었다. STL도 한동안 사용하지 않다가 사용하려니 실수가 많았다.

 

이 문제는 원래는 위상정렬이랑 DP 문제라는데, 위상 정렬로 풀기가 조금 애매해서 위상정렬 비스무리한 무언가로 풀게 되었다. 해결 방법은 이렇다. 맨 처음에 queue에(나는 그냥 vector를 사용했다) 처음부터 시작할 수 있는 건물들을 <건물 번호, 완공까지 남은 시간>의 pair로 집어넣는다. 그 다음 각 iteration에서 queue에 있는 건물들 중 가장 적은 시간이 남은 건물을 뽑아서 그 건물을 짓는다. 그리고 그 건물을 짓는 동안 소요된 시간들을 queue에 있는 모든 건물들에서 뺀다. 그리고 완공된 건물을 통해 새롭게 지을 수 있게 된 건물이 있다면 그 건물을 새로 queue에 집어넣는다.

 

이걸 반복하여 queue에서 최근에 나온 건물이 특정 건물(obj)이라면, 그 때의 시간을 출력하면 된다.

 

시간복잡도는

이렇게 될 거다. 문제에서 T의 범위가 안 나와서 조금 당황했는데 그냥 해보니까 다 맞았다.

 

위상 정렬 복습하고 다른 풀이 보러 가야겠다. . .

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
const int maxN = 1050;
 
int t, n, k;
int cnt[maxN], cost[maxN];
bool order[maxN][maxN];
bool chk[maxN];
int obj= 0;
vector<pair<int,int> > onBuild, temp;
    
void initVar() {
    onBuild.clear();
    temp.clear();
    
    for(int i =0 ; i < maxN; i++) {
        cnt[i]=0;
        chk[i] = false;
        cost[i] = 0;
        for(int j = 0 ; j<maxN; j++) {
            order[i][j] = false;
        }
    }
}
 
void scanVar() {
    
    int temp1, temp2;
    
    scanf("%d %d", &n, &k);
        
    for(int j = 1; j <= n; j++) {
        scanf("%d", &cost[j]);
    }
    
    for(int j = 0; j < k; j++) {
        scanf("%d %d", &temp1, &temp2);
        order[temp1][temp2] = true;
        cnt[temp2]++;
    }
    scanf("%d", &obj);
}
 
int findMinIndex() {
    int valueMin = 987654321;
    int minIndex = -1;
    for(int i = 0 ; i < onBuild.size(); i++) {
        if(onBuild[i].second < valueMin) {
            minIndex= i;
            valueMin = onBuild[i].second;
        }
    }
    return minIndex;
}
 
void subMinTime(int minIndex) {
    int minTime = onBuild[minIndex].second;
    temp.clear();
    for(int i = 0; i < onBuild.size(); i++) {
        pair<int, int> tempPair = onBuild[i];
        temp.push_back(tempPair);
    }
    onBuild.clear();
    for(int i = 0; i < temp.size(); i++) {
        if(i == minIndex) continue;
        onBuild.push_back(make_pair(temp[i].first, temp[i].second - minTime));
    }
}
 
void checkNewBuild(int index) {
    for(int i = 1 ; i<= n; i++) {
        if(order[index][i] == true) {
            cnt[i]--;
            if(cnt[i] == 0 && chk[i] == false) {
                onBuild.push_back(make_pair(i, cost[i]));
                
                chk[i] = true;
            }
        }
    }
}
 
int main ( void ) {
    freopen("/workspace/PS_Git/BOJ/1005/input.txt","r", stdin);
    
    int minIndex, minNum; //minIndex는 벡터상에서의 index, minNum은 건물 번호 
    int sum;
    
    scanf("%d", &t);
    for(int i = 0 ; i< t ; i++) {
        initVar();
        scanVar();
        minIndex= -1, minNum = -1;
        sum =0;
        
        for(int j = 1; j <= n; j++) { //initializing
            if(cnt[j] == 0) {
                onBuild.push_back(make_pair(j, cost[j]));
                chk[j] = true;
            }
        }
        
        
        
        while(minNum!= obj) {
            minIndex = findMinIndex();
            minNum = onBuild[minIndex].first;
            sum+= onBuild[minIndex].second;
            subMinTime(minIndex); //renewed onBuild vector
            checkNewBuild(minNum);
        }
        
        printf("%d\n", sum);
        
    }
    return 0;
    
}

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1005/1005.cpp

Jordano-Jackson/PS