[백준 1005] ACM Craft(C++)

- 접근 방법

 

문제를 읽고 dp와 위상정렬로 문제를 풀 것이라 생각했습니다. 위상정렬이란, 방향 그래프에서 적용되는 알고리즘으로 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용되는 알고리즘입니다. 

문제 예시를 보면, 2번 3번 건물은 1번 건물이 지어져야 지을 수 있고, 4번 건물은 2, 3번 건물들이 각각 지어져야 지을 수 있습니다. 문제에서 입력을 받을 때 마다 각 정점의 진입 차수를 증가시켜 자신의 priority를 기록하도록 합니다. N의 크기가 작기 때문에, 순차탐색을 이용하여 진입 차수가 낮은 것들을 큐에 넣고 bfs를 돌리는 방식으로 답을 구했습니다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define endl "\n"
 
size_t T, N, K, W, ans;
std::vector<int> building;
std::vector<int> entry_degree;
std::vector<int> building_cost_save;
std::vector<int> visited;
std::vector<std::vector<int> > building_cost;
std::queue<int> q;
 
void input_faster()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
}
 
void input()
{
    input_faster();
    std::cin >> T;
}
 
void solve_input()
{
    int a, b;
    std::cin >> N >> K;
    building = std::vector<int>(N + 1);
    entry_degree = std::vector<int>(N + 1, 0);
    building_cost_save = std::vector<int>(N + 1 , 0);
    visited = std::vector<int>(N + 1, 0);
    building_cost = std::vector<std::vector<int> >(N + 1);
    for (size_t i = 1 ; i <= N ; i++)
        std::cin >> building[i];
    for (size_t i = 0 ; i < K ; i++)
    {
        std::cin >> a >> b;
        building_cost[a].push_back(b);
        entry_degree[b]++;
    }
    std::cin >> W;
    q = std::queue<int>();
}
 
void input_queue()
{
    size_t i = 0;
    while(++i <= N)
    {
        if (!entry_degree[i] && !visited[i])
        {
            q.push(i);
            visited[i] = 1;
        }
    }
}
 
void solve()
{
    int val, x;
    solve_input();
    input_queue();
    while (q.front() != W)
    {
        val = q.front();
        q.pop();
        for (size_t i = 0 ; i < building_cost[val].size() ; i++)
        {
            x = building_cost[val][i];
            building_cost_save[x] = std::max({building_cost_save[x], building[x] + building_cost_save[val], building[x] + building[val]});
            entry_degree[x]--;
        }
        input_queue();
    }
    ans = std::max(building_cost_save[W], building[W]);
}
 
void print_val()
{
    std::cout << ans << endl;
}
 
int main()
{
    input();
    while (T--)
    {
        solve();
        print_val();
    }
    return (0);
}