[백준] 1005번 : ACM Craft

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

 

💡 접근법

• N은 10^3, D는 10^5 => 정답 영역은 10^8 (int 사용 가능)
• D는 0도 가능하다. 특정 노드에 도착했다고 바로 반환하면 안됨

건설이 동시에 가능하다는 것이 독특하다. 

• 선행 건물들 중 가장 큰 값만 채택하면 된다

문제에서 지정한 건물만 지을 수 있으면 되기 때문에, 모든 건물을 지을 필요는 없다.

역순으로 필수 건물부터 시작해서, BFS 로 조건 건물들을 순회하면 된다.

이렇게 가다보면 조건이 없거나, 이미 건설된 경우에 반환된다

 

건설 순서에 따라, 이미 지은 건물일 수 있으며, 실행 순서에 따라 이전에 계산했던 값이 필요한 상황이 생긴다

• 이전에 계산한 결과를 캐싱할 필요가 있다

여러 횟수를 반복하기 때문에 데이터를 다시 세팅하는 과정도 중요하다

 

➕ 짚고 넘어가기

• vector::resize(n, val) 는 처음 설정한 벡터 크기보다 늘어나는 값에 대해서만 val 로 초기화해준다. 반대로 더 적은 사이즈면 n만큼 잘라버린다. 
  
  • 이미 할당된 capacity는 그대로 유지한다

 

• vector::reserve(n) 으로 capacity를 지정해놓고 사용하면 메모리 재할당을 막을 수 있다.
  • 이 문제의 경우에 N의 값은 1000 고정이므로 resize를 쓰기보단 reserve를 해놓고 이후엔 memset만 하는게 나았을것같다.

 

🧪 테스트 케이스

//조금 큰 수 테스트
1
5 10
100000 99999 99997 99994 99990
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4

정답 : 399990

//다녀왔던 노드 재방문 테스트
1
5 5
1 1 1 1 1
1 2
2 3
3 5
3 4
4 5
5

정답 : 5

 

---

✏️ 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
1
5 10
100000 99999 99997 99994 99990
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4
*/

vector<int> Cost;
vector<vector<int>> Req;
vector<int> ConstructTime;

//@param Sum 지금까지 건설하면서 필요했던 누적 값
void FindMinCost(int CurrentNode, int Sum)
{
    if (ConstructTime[CurrentNode] != -1)
    {
        return;
    }

    //아직 건설이 필요하면 필요한 건물들에 대해 모두 함수 호출하고, 반환값들 받아주기
    int ReqTime = Sum;
    for (int ReqNode : Req[CurrentNode])
    {
        //동시 건설이 가능하기 때문에 반환값들 중 가장 큰 값만 채택한다
        FindMinCost(ReqNode, Sum);
        ReqTime = max(ReqTime, ConstructTime[ReqNode]);
    }
    ConstructTime[CurrentNode] = ReqTime + Cost[CurrentNode];
    return;
}

int main() {
    int T = 1;
    cin >> T;
    while(T > 0)
    {
        int N, K;
        cin >> N >> K;

        ConstructTime.clear();
        ConstructTime.resize(N+1, -1);
        
        Cost.clear();
        Cost.resize(N+1, 0);
        for(int i = 1;i <= N;i++)
        {
            cin >> Cost[i];
        }

        Req.clear();
        Req.resize(N+1);
        for (int i = 0;i < K;i++)
        {
            int X, Y;
            cin >> X >> Y;
            Req[Y].push_back(X);
        }

        int StartPos = 0;
        cin >> StartPos;

        FindMinCost(StartPos, 0);
        cout << ConstructTime[StartPos] << "\n";
        T--;
    }
    
    return 0;
}

 

 

✏️ 다른 사람의 풀이

 

다른 풀이를 보니 위상정렬을 써서 푸는 경우가 많았다

이 문제는 결과 노드를 미리주기 때문에, 거기부터 역산해서 DP와 BFS처럼 푸는게 가능했는데

 

한번에 많은 노드의 결과가 필요했다거나 하면 위상정렬을 무조건 쓸 수 밖에 없었을듯하다

 

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

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N >> K;

        vector<int> time(N + 1);           // 각 건물을 짓는 시간
        vector<int> indegree(N + 1, 0);   // 진입 차수
        vector<vector<int>> adj(N + 1);   // 건물 간 선행 관계 그래프
        vector<int> dp(N + 1, 0);         // 해당 건물까지 걸리는 최소 시간

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

        for (int i = 0; i < K; ++i) {
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            indegree[y]++;
        }

        int W;
        cin >> W;

        queue<int> q;
        // 진입 차수가 0인 노드들 큐에 넣기
        for (int i = 1; i <= N; ++i) {
            if (indegree[i] == 0) {
                q.push(i);
                dp[i] = time[i]; // 처음 건물은 자기 시간만큼 걸림
            }
        }

        // 위상 정렬과 DP 진행
        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (int next : adj[curr]) {
                dp[next] = max(dp[next], dp[curr] + time[next]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        cout << dp[W] << '\n';
    }

    return 0;
}