백준 1005번 [ACM Craft](C++) -yes6686- 티스토리

백준 문제 풀이: 1005 [ACM Craft]

---

문제 링크: https://www.acmicpc.net/problem/1005

문제 설명:

건물 건설 순서와 각 건물의 건설 시간을 이용해 특정 건물 완공까지 걸리는 최소 시간을 계산하는 문제입니다.

• 각 건물은 선행 건설 조건을 가집니다.
• 선행 조건이 충족된 후 해당 건물을 건설할 수 있습니다.
• 특정 건물 W를 완성하는 데 필요한 최소 시간을 구해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> v[1001];
queue<int> q;
int arr[1001];
int dp[1001];
int len[1001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;

        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            dp[i] = arr[i];
        }

        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            v[x].push_back(y);
            len[y]++;
        }

        int w;
        cin >> w;

        for (int i = 1; i <= n; i++) {
            if (len[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int k = q.front();
            q.pop();
            for (int i = 0; i < v[k].size(); i++) {
                int h = v[k][i];
                dp[h] = max(dp[h], arr[h] + dp[k]);
                len[h]--;
                if (len[h] == 0) {
                    q.push(h);
                }
            }
        }

        cout << dp[w] << '\n';

        for (int i = 1; i <= n; i++) {
            dp[i] = 0;
            arr[i] = 0;
            v[i].clear();
            len[i] = 0;
        }
    }
}

예제

입력:
2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
1 2 3 4 5 6 7 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 8
8

출력:
120
36

---

코드 설명

• 입력 처리: 건물 개수(n), 선행 조건 수(k), 각 건물의 건설 시간, 선행 조건(x, y), 목표 건물 W를 입력받습니다.
• 위상 정렬: 건물 간의 선행 조건을 그래프로 표현하고, 위상 정렬을 이용해 건설 순서를 결정합니다.
• 동적 프로그래밍: dp 배열에 각 건물까지 걸리는 최소 시간을 저장합니다.
• 출력: 목표 건물 W의 완공 시간을 출력합니다.

시간 복잡도

• 그래프 탐색: O(V + E) (건물 수와 간선 수)
• 최종 시간 복잡도: O(T * (V + E)) (테스트 케이스 T 포함)

---

결과

코드는 위상 정렬과 동적 프로그래밍을 결합하여 문제를 효율적으로 해결합니다. 추가적인 테스트를 통해 최적화를 확인할 수 있습니다.