[BOJ알고리즘, C++]#2637_장난감 조립, 위상 정렬, DP, 진입차수 BFS 위상 정렬

 

#1. 문제

 

2637번: 장난감 조립

 

---

 

#2. 풀이

 

1. 위상 정렬

 

[자료구조]#6_그래프

 

위상 정렬은 DAG(비순환 유향 그래프)에서 각 정점들의 선행 관계를 유지하며 정점을 나열하는 방법입니다. 위상 정렬 알고리즘은 일반적으로 스택자료구조와 재귀 DFS를 활용한 위상정렬, 그리고 진입 차수와 BFS를 활용하는 위상 정렬이 있습니다.

 

2. 거꾸로 위상 정렬 하자! 도착점을 시작점으로!

 

1. 먼저, 그래프 구성 과정에서 X를 위해 필요한 Y의 갯수를 입력받고, 기존의 Y -> X 방향성을 역으로 뒤집어, X -> Y 방향성을 갖는 간선을 전제로 그래프를 구성해 줍니다. 이때, Y의 진입 차수를 증가시 켜고, X의 기본 부품 여부(무엇으로도 만들어질 수 없는)를 거짓으로 설정해 줍니다.
2. 최종 부품(N번째 부품)을 출발 정점으로 진입차수 BFS를 활용한 위상 정렬을 수행합니다. BFS 과정에서 인접 정점 탐색 이전에 인접 정점이 현재 정점을 구성하기 위해 필요한 개수를 업데이트해줍니다.
3. 마지막으로, 기본 부품 여부가 참인 정점들의 최종 부품 구성에 필요한 총개수를 출력해 줍니다.

 

---

 

#3. 코드

 

/*
*   [문제] : 중간 부품과 이를 구성하는 기본 부품의 개수가 주어졌을 때, 최종 부품을 구성하는 기본 부품의 총 갯수
*   [설명]
            1. 우선, "최종 부품 -> 기본 부품"의 방향성을 갖는 그래프를 구성한다.(기존의 방식과는 역 방향으로 그래프 구성)
            2. 기본 부품(어떠한 부품으로도 구성할 수 없는 고유 부품)을 찾는다.
            3. 최종 부품을 시작으로 위상정렬을 시작해, DP를 통해 현재 부품을 구성하는데 필요한 중간 혹은 기본 부품의 개수를 계산해 나간다.
            4. 마지막으로 기본 부품과 최종 갯수를 오름차순으로 출력한다.
*/

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

#define MAX 101

int N,M;
vector<pair<int,int>> graph[MAX];
int inDegree[MAX] = {0,};
bool base[MAX];
int result[MAX] = {0,};

void TopologicalSort()
{
    queue<int> q;
    q.push(N);
    result[N] = 1;

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

        for(const auto& p : graph[cur])
        {
            int part = p.first;
            int num = p.second;

            result[part] += result[cur] * num;

            if(--inDegree[part] == 0)
            {
                q.push(part);
            }
        }
    }
}

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

    cin >> N >> M;

    fill_n(base, N+1, true);

    // #1 그래프 구성 : 최종 부품 -> 기본 부품의 방향성 그래프, [현재 부품][{필요 기본 부품, 개수}]
    while(M--)
    {
        // X를 만드는데, Y가 K개 필요함
        int X,Y,K;
        cin >> X >> Y >>K;

        graph[X].push_back({Y,K});
        inDegree[Y]++;
        base[X] = false;
    }

    TopologicalSort();

    // #1. 기본 부품의 번호와 개수를 오름차순으로 출력
    for(int i=1; i<=N; ++i)
        if(base[i])
            cout << i << ' ' << result[i] << '\n';


    return 0;
}

 

---