[백준] 2637: 장난감 조립 - 왜 위상정렬인가?

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

 

예제

7
8
5 1 2
5 2 2
7 5 2
6 5 2
6 3 3
6 4 4
7 6 3
7 4 5

출력 : 
1 16
2 16
3 9
4 17

---

하나의 완제품을 완성하는데 필요한 기본 부품의 수를 구하는 문제이다. 어떤 부품이 기본 부품인지를 구하고, 중간 부품을 기본 부품으로 치환하는 방식으로 풀이를 떠올렸다. dp를 사용한 방식인데 2차원 배열로 dp 배열을 선언해서 dp [i][j]를 i번 부품을 만드는데 필요한 j 부품의 수 (j는 기본 부품)로 생각하고 구현했다. 해당 풀이의 점화식은 다음과 같다.

i번 부품에 대해(i는 중간 부품) dp[i] = dp [next.first] * next.second. next는 i번 부품을 만드는데 필요한 부품이다.

 

백준에서 제시하는 풀이는 내가 생각한 풀이처럼 단순히 중간 부품을 오름차순으로 풀어도 정답이 나왔다. 그러나 해당 풀이는 i번 부품이 아직 기본 부품으로 치환되지 않은 다른 부품을 사용하는 경우를 고려하지 못했고, 따라서 중간 부품을 계산하는 순서가 중요하다는 것을 포인트로 풀이를 다시 생각해보았다.

 

기본 부품으로만 이루어진 중간 부품의 dp 값, 즉 필요한 기본 부품의 수를 모두 계산하고 계산된 중간 부품을 사용하는 중간 부품을 계산해야 한다.

 

예를 들어 생각해 보자. 아래의 사진은 백준 예시를 그래프로 나타낸 것이다.

6번 부품의 계산은 반드시 5번 부품을 계산한 뒤에 이루어져야 한다.  7번은 5, 6을 계산한 뒤에 이루어져야 한다. 이 부분에서 위상 정렬이 필요하다고 생각했고 기존에 설정한 dp 배열의 정의는 그대로 가져갔다. 위상 정렬의 편의성을 위해 dp 점화식을 조금 변경했는데

기존 dp [i] = dp [next.first] * next.second. next에서

dp [next.first] = dp [i] * next.second로 변경했다. 사실 점화식만 보면 이렇게 바꿔도 되나 싶은데 기존에는 5번 부품을 계산할 때 next를 1, 2번으로 설정한 것이고 이번에는 1, 2번의 next를 5번으로 변경한 것뿐이다.

 

아무튼 중요한 건 중간 부품을 계산하는 순서가 존재한다는 것이고 이를 위상 정렬로 해결할 수 있다는 것이다!

dp 부분의 코드만 자세히 보자.

while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (auto next : adj[cur])
        {
            indegree[next.first]--;
            if (indegree[next.first] == 0)
                q.push(next.first);

            for (int j = 1; j <= n; j++)
            {
                dp[next.first][j] += dp[cur][j] * next.second;
            }
        }
    }

생각해 두었던 점화식을 그대로 구현하면 된다.

 

/** 위상정렬 2637 장난감 조립 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int n, m;
int indegree[103];
int dp[103][103];
int basic[103];
vector<pair<int, int>> adj[103];
queue<int> q;
// adj[i]={a, b} : i를 만드는데 a가 b개 필요함.

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[b].push_back({a, c});
        indegree[a]++;
    }

    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0)
        {
            basic[i] = 1;
            q.push(i);
            dp[i][i] = 1;
        }
    }

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (auto next : adj[cur])
        {
            indegree[next.first]--;
            if (indegree[next.first] == 0)
                q.push(next.first);

            for (int j = 1; j <= n; j++)
            {
                dp[next.first][j] += dp[cur][j] * next.second;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (basic[i])
            cout << i << ' ' << dp[n][i] << '\n';
    }
}