[백준 2637] 장난감 조립

문제 링크 => 2637번: 장난감 조립 (acmicpc.net)

2637번: 장난감 조립

---

위상정렬 기본문제이다.

 

이 문제를 접근하기 위해 2차원 배열 result[x][y]를 설정하였다. (x번 부품에 대한 y번 부품의 갯수)

 

1. inDegree[x] == 0 이 되는 x는 기본 부품이며 기본 부품의 수를 1로 초기화 하고 기본 부품을 저장하도록 하는 벡터를 설정하여 push_back 해준다. => result[x][x] = 1 (x번 부품에 대한 x번 부품의 갯수 1로 설정)

 

2. 위상정렬을 진행하면서 임의의 x번 부품의 다음 번호의 부품을 next라고 할 때, next 번 부품에 대한 x번 부품의 필요한 갯수 cnt에 대하여 기본 부품을 저장해둔 벡터 tool_V 에 대하여 다음과 같이 정리할 수 있다

int next = v[x][i].first;
int cnt = v[x][i].second;
for (int j = 0; j < tool_V.size(); j++) {
	int tool = tool_V[j];
	result[next][tool] += cnt * result[x][tool];
}

즉, next 번 부품에 대하여 tool 번 기본 부품의 갯수를 임의의 x번 부품에 대한 tool 번 기본 부품의 갯수에 cnt 값을 곱하여 더해주면 된다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int inDegree[101];
vector<pair<int, int>> v[101];
int result[101][101];

void solve(int n) {
	queue<int> q;
	vector<int> tool_V;
    
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) {
			q.push(i);
			tool_V.push_back(i);
			result[i][i] = 1;
		}
	}

	while (!q.empty()) {
		int x = q.front();
		q.pop();
        
		for (int i = 0; i < v[x].size(); i++) {
			int next = v[x][i].first;
			int cnt = v[x][i].second;
            
			for (int j = 0; j < tool_V.size(); j++) {
				int tool = tool_V[j];
				result[next][tool] += cnt * result[x][tool];
			}
            
			if (--inDegree[next] == 0) {
				q.push(next);
			}
		}
	}

	for (int i = 0; i < tool_V.size(); i++) {
		cout << tool_V[i] << " " << result[n][tool_V[i]] << endl;
	}
    
    return;
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, cnt;
		cin >> x >> y >> cnt;
		v[y].push_back({ x,cnt });
		inDegree[x]++;
	}

	solve(n);

	return 0;
}