[C++] 백준 2637 장난감 조립

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

2637번: 장난감 조립

문제 해결

• 위상정렬 문제라는 것을 쉽게 알 수 있다.
• 가장 마지막에 완제품 n이 오므로 n부터 시작해서 앞에 제품들을 조사한다.

CODE

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int, int>> adj[101];
int in[101], cnt[101];
int main() {
	int n;
	cin >> n;
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x, y, k;
		cin >> x >> y >> k;
		adj[x].push_back({ y, k });
		in[y]++;// y 앞에 있는 숫자 개수
	}
	vector<int> ans;
	queue<int> que;
	que.push(n);
	cnt[n] = 1; // n은 첫 번째이므로 1
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		if (adj[cur].empty()) {
			ans.push_back(cur);
		}
		for (auto p : adj[cur]) {
			int nxt = p.first;
			int c = p.second;
			cnt[nxt] += cnt[cur] * c;
			if (--in[nxt] == 0) que.push(nxt);
		}
	}
	sort(ans.begin(), ans.end());
	for (auto k : ans) cout << k << ' ' << cnt[k] << '\n';
	return 0;
}