[C++/백준] 1516번: 게임 개발*

문제 링크

1516번: 게임 개발

 

풀이

그냥 위상 정렬인줄 알았지만.. 동시에 건물을 지을 수 있는 것을 간과해버려서 조금 헷갈렸다.
3번째 건물을 지으려면 10시간이 걸리고, 1과 2번째 건물을 지어야 가능하다고 할 때,
1번째 건물을 짓는 데에 1시간, 2번째 건물을 짓는 데에 3시간이 걸린다고 해보자.
1번째와 2번째 건물을 서로 간섭하는 게 없으니 동시에 짓고, 더 오래 걸리는 2번째 건물을 짓고 나서 3번째 건물을 지을 수 있다.
그러므로 우선순위 큐를 이용해 지어주어야 한다.

1. 입력 받으며 인접리스트와 진입차수 벡터를 만든다.
2. 위상 정렬을 진행할 큐는 오름차순 우선순위 큐로 만들어서 더 빨리 걸리는 건물을 먼저 짓도록 한다.
3. n번 반복하여 위상 정렬을 실행한다.
   1. cur 노드와 연결된 노드들의 진입차수가 0이 되면 q에 추가한다.
   2. pair로 넣는데, 첫번째 요소는 현재 건물을 짓는 시간+그 건물을 짓기 전 지은 건무들의 시간이 될 것이다.
   3. q에서 뽑을 때, answer 값을 갱신한다.
4. answer를 출력한다.

 

코드

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

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

    int n;
    cin >> n;
    vector<int> time(n + 1);
    vector<vector<int>> adj(n + 1);
    vector<int> inDegree(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> time[i];
        int tmp;
        while (cin >> tmp)
        {
            if (tmp == -1) break;
            adj[tmp].push_back(i);
            inDegree[i]++;
        }
    }

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    for (int i = 1; i <= n; i++)
    {
        if (inDegree[i] == 0) pq.push({ time[i], i });
    }

    vector<int> answer(n + 1);
    for (int i = 1; i <= n; i++)
    {
        if (pq.empty()) break;
        int cur = pq.top().second;
        int curTime = pq.top().first;
        answer[cur] = curTime;
        pq.pop();
        for (int j = 0; j < adj[cur].size(); j++)
        {
            int next = adj[cur][j];
            if (--inDegree[next] == 0)
            {
                pq.push({curTime+time[next], next});
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        cout << answer[i] << '\n';
    }
}