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

문제

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

풀이

각 건물마다 선행되어 지어져야할 건물이 존재하기 때문에 위상정렬 문제입니다.

 

건물마다 들어오는 화살표(indegree)를 저장하고, 자신이 탐색될 때마다 화살표를 하나씩 지우며 화살표의 개수가 0이 될 경우 자신의 건물을 짓고 다음 탐색을 진행합니다.

 

이때 각 건물들은 독립적으로 지어질 수 있기 때문에 먼저 지어진 건물들을 우선적으로 처리하기 위해 BFS탐색에 우선순위 큐를 활용합니다. 큐에 (건물 번호, 걸린시간)을 넣고, 지어질때까지 걸린 시간이 빠른 건물 순서로 큐에서 출력되도록 합니다. 큐에서 나온 건물이 W라면 그때의 걸린 시간을 출력하고 탐색을 종료합니다.

 

 

예시

위와 같은 그래프가 주어졌을 때 8번 건물을 짓는데의 최소시간을 구하는 문제를 예로 들어 설명해보겠습니다. 

 

우선 처음 시작은 받는 화살표가 없는 1, 2가 우선순위 큐에 들어갑니다. 우선 순위 큐에는 (건물 번호, 해당 건물이 다 지어졌을 때의 시간) 쌍으로 들어갑니다.

• priority queue : {1, 10}, {2, 5}

 

우선 순위 큐에 의해 {2, 5}가 출력 됩니다. 하지만

 4번 건물은 1번 건물이 선행되어야 하기 때문에 아직 지을 수 없습니다.

• priority queue : {1, 10}

 

 

{1, 10}이 출력됩니다. 

큐에는 새롭게 {3, 10 + 1}, {4, 10 + 15} 가 들어갑니다.

• priority queue : {4, 25}, {3, 11}

 

{3, 11} 출력됩니다. 

큐에는 새롭게 {5, 11 + 3}이 들어갑니다.

• priority queue : {4, 25}, {5, 14}

 

 

{5, 14} 출력

8번 건물을 짓기 위한 6번 건물이 아직 지어지지 않았으므로 큐에는 8번 건물을 넣을 수 없습니다.

• priority queue : {4, 25}

 

{4, 25} 출력

큐에는 {6, 25 + 5}, {7, 25 + 10} 가 입력됩니다.

• priority queue : {7, 35}, {6, 30}

 

{6, 30} 출력

 

큐에는 {8, 30 + 5} {9, 30 + 3}가 입력됩니다.

• priority queue : {8, 35}, {7, 35}, {9, 33}

 

{9, 33} 출력

• priority queue : {8, 35}, {7, 35}

 

{7, 35} 출력

• priority queue : {8, 35}

 

{8, 35} 출력

이 때 우리가 구할 8번 건물이 큐에서 출력되었으므로 8번까지 짓는데에 걸린 35가 최소시간이 됩니다.

 

 

한 건물을 짓는데에 걸리는 시간을 해당 건물에서 나가는 간선의 가중치라 생각하고 문제를 해결하면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Node
{
    int num;
    int endTime;

};

bool operator>(const Node a, const Node b)
{
    return a.endTime > b.endTime;
}

int n, k;
int target;
vector<int> buildTime;
vector<vector<int>> edges;
vector<int> indegree;
vector<int> answer;

void input()
{
    cin >> n >> k;
    buildTime.assign(n+1, 0);
    edges.assign(n+1, vector<int>());
    indegree.assign(n+1, 0);

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

    for (int i=0; i<k; ++i)
    {
        int from, to;
        cin >> from >> to;
        ++indegree[to];
        edges[from].push_back(to);
    }
    
    cin >> target;
}

void topologicalSort()
{
    priority_queue<Node, vector<Node>, greater<Node> > pq;
    for (int i=1; i<n+1; ++i)
    {
        if (indegree[i] == 0)
            pq.push({ i, buildTime[i] });
    }

    while(!pq.empty())
    {
        int cur = pq.top().num;
        int curTime = pq.top().endTime;
        pq.pop();

        if (cur == target)
        {
            answer.push_back(curTime);
            break;
        }

        for (int next : edges[cur])
        {
            --indegree[next];
            if (indegree[next] != 0)
                continue;

            int nextTime = curTime + buildTime[next];
            pq.push({next, nextTime});
        }
    }
}

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

    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        input();
        topologicalSort();
    }

    for (auto a : answer)
    {
        cout << a << "\n";
    }
    return 0;
}