[백준 c++] 1005 ACM Craft

문제

https://www.acmicpc.net/problem/1005
어떤 건물을 짓는데 규칙이 존재한다.
예를 들어, 규칙은 다음과 같은 형식이다 => 3 4
이 규칙은 3번 건물 다음에 4번 건물을 지을 수 있다는 의미다.

N개의 건물의 건설에 걸리는 시간이 주어지고, K개의 규칙이 주어질 때 건물 W를 건설하는데 드는 최소 시간을 구하는 문제다.

---

풀이

이전에 풀었던 1516 게임개발 문제랑 똑같은 문제로 DFS + DP를 이용해서 풀 수 있다.

1. 배열 벡터 vector<int> map[1001] 를 사용해서 각 건물마다 선행되어야 하는 건물을 저장한다.
   예를 들어, 3번 건물을 짓기 위해 1,2 번 건물을 먼저 지어야 한다면 map[3]에 1,2를 push_back해준다.

2. 구해야하는 값인 w부터 선행되어야하는 건물들을 탐색해준다.

예시

map[1] = []
map[2] = [1]
map[3] = [1, 2]

위와 같이 map이 구성됐을 때 w가 3이라면 탐색 순서는 다음과 같다.
탐색하면서 얻은 값은 메모이제이션해준다.

//입출력이 많을 땐 꼭 써주자^^
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int t, n, k, a, b, w, delay[1001], dp[1001];
vector<int> map[1001];

int dfs(int idx)
{
    if (!map[idx].size())
        return delay[idx];

    if (dp[idx] != -1)
        return dp[idx];

    for (int i = 0; i < map[idx].size(); i++)
    {
        int x = map[idx][i];
        dp[idx] = max(dp[idx], dfs(x) + delay[idx]);
    }
    return dp[idx];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
            cin >> delay[i];
            dp[i] = -1;
        }
        for (int i = 0; i < k; i++)
        {
            cin >> a >> b;
            map[b].push_back(a);
        }
        cin >> w;
        cout << dfs(w) << "\n";
        for (int i = 1; i <= n; i++)
        {
            map[i].clear();
        }
    }
}