[BOJ] 2637번 | 장난감 조립 (C++)

🔗문제 보러가기

2637번: 장난감 조립

 

👨‍💻풀이 과정

 

위상 정렬과 다이나믹 프로그래밍을 통해 풀었습니다. 처음에는 DFS로 풀 수 있을 것 같단 생각에 도전하려고 했는데, 중복되는 계산이 너무 많아 시간 초과가 날 것 같단 생각이 들어 그 풀이는 포기했습니다. 아무튼, 제가 어떻게 풀었는지 천천히 설명해 드리도록 하겠습니다.

 

 

1. 간선 정보 및 진입 차수 설정

 

하위 부품에서 상위 부품으로 간선이 가리키도록 방향을 설정하였고, 필요한 부품 개수 정보도 같이 관리하였습니다.

#include <vector>
using namespace std;
using Part = pair<int, int>;	// <부품 번호, 필요한 개수>


int main() {
    int N, M;
    cin >> N >> M;
    
    // 간선 정보 및 진입 차수 정보 등록
    vector<vector<Part>> parts(N + 1, vector<Part>());
    vector<int> inDegrees(N + 1);
    int upperPart, lowerPart, count;

    for (int i = 0; i < M; i++) {
        cin >> upperPart >> lowerPart >> count;
        
        parts[lowerPart].emplace_back(upperPart, count);
        inDegrees[upperPart]++;
    }
    
    //...
}

 

문제에 나와있던 예제를 통해 그래프를 구성하면 다음과 같습니다.

 

그래프

 

 

2) 2차원 DP 배열을 통한 기본 부품 개수 기억

 

2차원 배열 DP를 선언합니다. DP[i][j]의 뜻은 i번 부품을 1개 만드는데 필요한 j번 부품의 전체 개수라는 뜻이죠.

예를 들어, 6번 부품을 만드는 데 필요한 1번 부품의 총 개수 DP[6][1] = 4 가 될 겁니다. 이와 같은 방식으로 저장해 줄 겁니다.

 

그러기 위해, 1번 부품부터 N번 부품까지 순회하며 진입 차수가 0인 부품 i를 찾습니다.

진입 차수가 0이라는 것은 기본 부품이라는 것을 의미하기 때문이죠.

 

부품 i를 찾았다면, 위상 정렬을 위한 큐(Queue)에 집어 넣음과 동시에, DP[i][i] = 1로 초기화 해주도록 합니다.

*(기본 부품인 자기 자신을 만드는 데 필요한 개수는 1이기 때문이죠.)

vector<vector<int>> dp(N + 1, vector<int>(N + 1));
queue<int> nextParts;

for (int i = 1; i <= N; i++) {
    if (inDegrees[i] == 0) {
        dp[i][i] = 1;
        nextParts.push(i);
    }
}

 

위에서 봤던 예제를 토대로 이 과정을 진행해준다면, 다음과 같은 2차원 배열이 될 겁니다.

 

기본 부품으로 초기화 된 2차원 DP 배열

 

이제 위상 정렬 알고리즘을 적용해 줍시다.

for (int i = 1; i <= N; i++) {
    int lowerPart = nextParts.front();
    nextParts.pop();

    for (const auto& upperLevel : parts[lowerPart]) {
        int upperPart = upperLevel.first;
        int upperPartCount = upperLevel.second;
        
        // -------중요-------
        for (int i = 1; i <= N; i++)
            dp[upperPart][i] += dp[lowerPart][i] * upperPartCount;
        // -------중요-------

        if (--inDegrees[upperPart] == 0)
            nextParts.push(upperPart);
    }
}

 

DP[i] 행에는 i번 부품 1개를 만들기 위해 필요한, 모든 부품 재료 개수가 들어있습니다.

예제에서 5번 부품을 만들기 위해선, 1번 부품 2개와 2번 부품 2개가 필요하다고 나와 있습니다.

 

그렇다면 1번 부품을 만드는 데 필요한 i 번째 부품 * 2 한 값을 5번 부품을 만드는 데 필요한 i 번째 부품 개수에 더해줘야겠죠. 마찬가지로 2번 부품을 만드는 데 필요한 i 번째 부품 * 2 한 값을 5번 부품을 만드는 데 필요한 i 번째 부품 개수에 더해주면 될 겁니다. 

 

이걸 코드 상으로 나타낸 게 다음 코드입니다.

for (int i = 1; i <= N; i++)
    dp[upperPart][i] += dp[lowerPart][i] * upperPartCount;

 

이 부분만 추가해주고, 나머지는 위상 정렬을 해주면 됩니다.

위상 정렬이 끝났다면, dp[N]에 해당하는 행에서 0을 제외한 값들을 차례대로 출력해주면 됩니다.

* dp[N][5] = 0 이라는 것은 5번 부품이 기본 부품이 아니라는 걸 뜻하기 때문이죠.

 

 

✏️소스 코드 및 결과

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

using namespace std;
using Part = pair<int, int>;    // <부품 번호, 필요 개수>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

vector<int> Solution(const vector<vector<Part>>& parts, vector<int>& inDegrees, int N) {
    vector<vector<int>> dp(N + 1, vector<int>(N + 1));
    queue<int> nextParts;

    for (int i = 1; i <= N; i++) {
        if (inDegrees[i] == 0) {
            dp[i][i] = 1;
            nextParts.push(i);
        }
    }

    for (int i = 1; i <= N; i++) {
        int lowerPart = nextParts.front();
        nextParts.pop();

        for (const auto& upperLevel : parts[lowerPart]) {
            int upperPart = upperLevel.first;
            int upperPartCount = upperLevel.second;

            for (int i = 1; i <= N; i++)
                dp[upperPart][i] += dp[lowerPart][i] * upperPartCount;

            if (--inDegrees[upperPart] == 0)
                nextParts.push(upperPart);
        }
    }

    return dp[N];
 }


int main() {
    FAST_IO
    int N, M;
    cin >> N >> M;

    vector<vector<Part>> parts(N + 1, vector<Part>());
    vector<int> inDegrees(N + 1);
    int upperPart, lowerPart, count;

    for (int i = 0; i < M; i++) {
        cin >> upperPart >> lowerPart >> count;
        parts[lowerPart].emplace_back(upperPart, count);
        inDegrees[upperPart]++;
    }

    vector<int> answers = Solution(parts, inDegrees, N);

    for (int i = 1; i <= N; i++) {
        if (answers[i] != 0)
            cout << i << " " << answers[i] << "\n";
    }    

    return 0;
}