[BOJ] ACM Craft(1005)

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

문제 : BOJ_1005번 이모티콘

문제 설명

위상정렬, dp, bfs

각 건물마다 그 건물을 짓기 위해서 먼저 지어져야 하는 건물들이 존재하고, 먼저 지어야 하는 건물이 없는 건물부터 시작하여 지정된 거물을 지을 때까지 걸리는 최소 시간을 작성하는 문제입니다.
건물에 대한 앞뒤 관계가 있고, 사이클이 아니기 때문에 indegree를 이용한 위상정렬 문제입니다.

그리고 먼저 지어야 하는 모든 건물이 지어져야 다음 건물이 지어지므로, dp를 활용하여 건물이 지어질 수 있는 최소 시간을 구할 수 있습니다.

---

Solution

한 건물이 지어지는 시간을 모두 입력받고(wait[]), 최종적으로 그 건물이 지어질 수 있는 최소 시간에 대한 배열을 만든 뒤(res[]), 위상정렬을 통해 정점에 대해 이어진 indegree를 전부 탐색하며 그 건물이 지어질 수 있는 시간들을 건물마다 각각 찾아내 배열에 넣고, 문제에서 주어진 res 값을 출력해주는 방식으로 풀어야 합니다.

---

Description

1. 테스트 케이스가 끝날 때마다 각 배열을 초기화해줘야 합니다. (memset)
   
2. 먼저 지어야 하는 건물이 없는 건물들은 그 건물이 지어지는 시간 자체가 최소 시간으로 지어질 수 있는 시간이므로, indegree[i] == 0 인 i 번 째 건물들은 모두 res[i] = wait[i];로 할당해줘야 합니다.
   

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int main(void) {
    int roof;
    cin >> roof;
    for (int i = 0; i < roof; i++) {
        vector<int>adj[1001];
        queue<int>q;
        int n, m, indegree[1001] = { 0, }, res[1001], wait[1001];
        memset(indegree, 0, sizeof(indegree)); // 테스트케이스 마다 memset으로 초기화
        memset(res, 0, sizeof(res));
        memset(wait, 0, sizeof(wait));
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> wait[i];
        }
        for (int i = 1; i <= m; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            indegree[b]++; // 전후 관계를 연결할 때 마다 indegree[]를 올려줍니다.
        }
        int fin;
        cin >> fin;
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) q.push(i);
            res[i] = wait[i];
        }
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = 0; i < adj[now].size(); i++) {
                int next = adj[now][i];
                res[next] = max(res[next], res[now] + wait[next]); // max()를 이용해 모든 indegree를 확인해주고 그 중 최댓값을 res[i]에 할당합니다.
                indegree[next]--;
                if (indegree[next] == 0) q.push(next);
            }
        }
        cout << res[fin] << endl;
    }
    return 0;
}