9주차(위상정렬) - [C++]백준1516 게임 개발

14 May 2022 in Study on Algorithm

백준1516 게임 개발 링크

문제

예제 입력

---

코드

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

// 각 선개발 수, 개발 시간, 개발결과
int cnt[501], cost[501], result[501];
// 인접행렬
vector<int> vec[501];
int n;

void topology_sort() {
    queue<int> q;
    // 처음 지점 추가
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0) {
            result[i] = cost[i];
            q.push(i);
        }
    }

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        // 다음 지점 탐색
        for (int i = 0; i < vec[cur].size(); i++) {
            int nxt = vec[cur][i];
            cnt[nxt]--;
            result[nxt] = max(result[nxt], result[cur] + cost[nxt]);
            if (cnt[nxt] == 0) {
                q.push(nxt);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << result[i] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a;
        cost[i] = a;

        while (true)
        {
            cin >> b;
            if (b == -1)
                break;
            vec[b].push_back(i);
            cnt[i]++;
        }
    }
    topology_sort();
}

설명

이 문제는 스타크래프트에서 팩토리를 짖기 위해 배럭을 먼저 짖는 것처럼 선건설 건물이 있는데 모든 건물마다 완성되는 시간을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 queue를 사용하여 구현했습니다. 앞에서 했던 작업 문제와 거의 같은데 다른점은 선건설에 대한 정보를 받을 때 무한 반복문으로 -1이 입력될때까지 받으며 출력할때 최대 시간이 아닌 각각의 건물이 건설되는 시간을 출력합니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과