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

백준의 ACM Craft(1005) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

순서가 정해진 건물들을 지을 때, 최종적으로 특정 'W'번 건물을 최소 몇 초 만에 지을 수 있는지 구해야 하는 문제이다.

본인은 이 문제를 "일을 처리하는데 그 순서를 정렬하는 위상정렬" 방식을 이용해서 접근해 보았다.

위상정렬에 대해서 따로 포스팅을 하지 않아서, 간단하게만 위상정렬에 대해서 먼저 알아보자.

위상정렬은 위에서 말했듯이 "일을 처리하는 순서를 결정" 하는 것이다.

이 문제도 마찬가지로, 먼저 지을 수 있는 건물이 있고, 특정 건물을 짓지 않으면 지을 수 없는 건물들이 존재한다.

즉, "건물을 짓는 순서를 결정" 해서 'W'번 건물이 몇 초에 지어지는지만 구하면 되므로 위상정렬을 이용해보았다.

또한, 이 문제는 위상정렬을 하면서 일의 순서를 정하는 과정에서 해당 일을 처리하는데 걸리는 최소시간을 구해야 하기

때문에 "해당 일을 처리하는데 걸리는 최소시간을 저장하는 배열" 을 하나 만들어서 관리해 주었다.

Result_Time[] 이라는 1차원 int형 배열을 사용해 주었다.

Result_Time[a] = b 의 의미는 "a번 건물을 짓는데 걸리는 최소시간은 b초입니다." 를 의미한다.

위상정렬이 동작하는 Queue의 반복문 안에서 위의 배열 값 또한 계속해서 갱신해 주면서 진행하였다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, K, D, W;
int Time[MAX];
int Result_Time[MAX];
int Entry[MAX];
vector<int> Build[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    memset(Time, 0, sizeof(Time));
    memset(Result_Time, 0, sizeof(Result_Time));
    memset(Entry, 0, sizeof(Entry));
    for (int i = 0; i < MAX; i++) Build[i].clear();
}
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> Time[i];
    for (int i = 0; i < K; i++)
    {
        int a, b; cin >> a >> b;
        Build[a].push_back(b);
        Entry[b]++;
    }
    cin >> W;
}
 
void Solution()
{
    queue<int> Q;
    for (int i = 1; i <= N; i++)
    {
        if (Entry[i] == 0)
        {
            Q.push(i);
            Result_Time[i] = Time[i];
        }
    }
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front();
        Q.pop();
 
        for (int i = 0; i < Build[Cur].size(); i++)
        {
            int Next = Build[Cur][i];
            Result_Time[Next] = Bigger(Result_Time[Next], Result_Time[Cur] + Time[Next]);
            Entry[Next]--;
 
            if (Entry[Next] == 0) Q.push(Next);
        }
    }
 
    cout << Result_Time[W] << endl;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}