[백준/c++] 1005번: ACM Craft

 

 

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

1005번: ACM Craft

 

문제 요약

 

건물을 짓는 순서가 정해져 있지 않다. 즉, 첫번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다.

매 게임 시작 시 건물을 짓는 순서가 주어진다. 또한, 모든 건물은 각각 건설을 시작해 완성될 때까지 delay가 존재한다.

 

이번 게임에선 위와 같이 건설 순서 규칙이 있다.

1번 건설 완료 → 2번, 3번(동시 진행 가능) → 4번 건설(2번과 3번 모두 건설 완료되어야만 가능)

4번 건물을 건설 완료하려면 10(1번) + 100(3번) + 10(4번) = 120초 소요

 

특정 건물을 가장 빨리 지을 때까지 걸리는 최소 시간을 알아내라.

 

 

범위

 

• 건물의 개수 N: 2 ≤ N ≤ 1000
• 건설 순서 규칙 개수 K: 1 ≤ K ≤ 100,000
• 건설에 걸리는 시간 Di: 0 ≤ Di ≤ 100,000, Di는 정수

 

입력 값

 

T(테스트케이스 개수)

N(건물 개수) K(건설 순서 규칙 개수)

건물당 건설에 걸리는 시간 Di

건설 순서 X Y (K개)

건설할 건물의 번호 W

 

 

---

 

sum [] 배열에는 해당 건물의 건설이 완료될 때까지 걸리는 시간을 저장한다.

 

1. 들어오는 간선이 없는 정점(건물)부터 시작 (queue에 넣기) -> 여기서 해당 건물의 건설이 완료될 때까지 걸리는 시간을 저장한다. 들어오는 간선이 없기 때문에 자기 자신(건물)의 건설에 걸리는 시간만 들어간다.

2. 연결된 정점들을 돌면서 다음 건물의 건설 시간을 더한 값을 넣어준다.

 

→ 여기서 ✨더 오래 걸리는 건물의 값을 넣어줘야 한다. 왜냐하면 자신에게로 들어오는 간선 중에서 제일 오래 걸리는 시간을 더해야 하기 때문이다. 4번 건물의 경우, 2번과 3번 건물이 이전 차례인데 2번의 시간은 필요 없다. 3번의 건물 건설이 완료되지 않으면 4번은 시작할 수 없으므로 더 오래 걸리는 값을 넣어주도록 한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define NUM 1002
using namespace std;
int t, n, k, w, T[NUM], sum[NUM], indeg[NUM], X, Y;
vector<int> graph[NUM];

void solution(){
    queue<int> q;
    //1. 들어오는 간선이 없는 정점부터 시작 -> queue에 넣기
    for(int i=1; i<=n; i++) if(indeg[i] == 0) {q.push(i); sum[i] = T[i];}

    while(!q.empty()){
        int x = q.front(); q.pop();
        for(int i : graph[x]){
            indeg[i]--;
            if(indeg[i] == 0) q.push(i);
            sum[i] = max(sum[i], sum[x]+T[i]); //더 큰 값 (더 오래 걸리는 시간을 합해야 하므로)
        }
    }
    cout << sum[w] << '\n';
}

void input(){
    cin >> t;
    while(t--){
        cin >> n >> k;
        for(int i=1; i<=n; i++) {
            cin >> T[i];        //건물 당 걸리는 시간
            indeg[i] = 0;       //초기화
            sum[i] = 0;         //초기화
            graph[i].clear();   //초기화
        }
        for(int i=1; i<=k; i++){
            cin >> X >> Y;
            graph[X].push_back(Y);
            indeg[Y]++;
        }
        cin >> w;
        solution();
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!