2025.02.23 (일요일)

위상정렬(1516 번)

#include <iostream> //c++
#include <stdio.h> //c
#include <vector> //c++ 배열
#include <algorithm> // 탐색, 정렬 등 알고리즘
#include <utility> // 
#include <string>
#include <string.h>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>

#define fio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // input, output 빠르게 하는 거
#define ll long long // long long이 너무 기니까 ll로 줄여요
#define pii pair<int,int> // pair<int,int>가 너무 길어요 그래서 pii로 줄여요
#define pll pair<ll,ll> // pair<long long, long long> 이 너어어어무 길어요. 그래서 pll로 줄여요
#define MOD 1e9+7 // 모듈러 계산할 때 쓰이는 값, 근데 문제마다 바뀌니까 알아서 바꾸세요

using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin>>n; // 건물의 개수
    vector<int> time(n+1); // 건물 짓는데 걸리는 시간
    vector<int> graph[n+1]; // 이 건물을 지으면 지을 수 있는 건물의 리스트
    vector<int> degree(n+1,0); // 각 건물의 차수, 0으로 초기화
    vector<int> dp(n+1,0); // 각 건물이 완성되는 최소 시간 저장

    for (int i=1;i<=n;i++) {
        cin>>time[i]; // 이 건물을 짓는데 걸리는 시간

        while (true) {
            int tmp; cin>>tmp; // 배럭 입력
            if (tmp==-1) break;

            graph[tmp].push_back(i); 
            degree[i]++; // 차수 증가
        }
    }

    // bfs

    queue<int> q; // 우선순위 큐: 완성되는 순서가 중요할 때, 큐: 완성한 결과가 중요할 때

    for (int i=1;i<=n;i++) {
        dp[i]=time[i]; // 이 건물을 짓는 시간 저장

        if (degree[i]==0) {
            q.push(i); // 차수가 0인 노드를 큐에 삽입
        }
    }

    while (!q.empty()) {
        int cur=q.front();
        q.pop();

        for (int nxt:graph[cur]) { // 현재 건물을 짓고 다음에 지을 수 있는 건물 탐색
            degree[nxt]--;

            if (degree[nxt]==0) q.push(nxt); // 지을 수 있다면(차수가 0이면) 큐에 삽입

            dp[nxt]=max(dp[nxt],time[nxt]+dp[cur]); // 완성될 건물은 이전에 걸린 시간과 이 건물을 지을 시간을 더한 만큼 걸림
        }
    }

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

    return 0;
}

//위상정렬