BOJ2637/ C++

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

2637번: 장난감 조립

백준 온라인저지 2637번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define MAX 101

using namespace std;


int require_parts[MAX];
int degree[MAX];
vector <pair<int, int>>v[MAX];
vector <int> nomal_parts;

int N,M;
int X, Y, K;

void Input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> X >> Y >> K;
		v[X].push_back({ Y,K });
		degree[Y]++;
	}
}

void solution() {
	queue<int>q;
	q.push(N);
	require_parts[N] = 1;
	while (!q.empty()) {
		int current = q.front();
		q.pop();

		if (v[current].empty())
			nomal_parts.push_back(current);

		for (int i = 0; i < v[current].size(); i++) {
			int parts_idx = v[current][i].first;
			int parts_cnt = v[current][i].second;
			require_parts[parts_idx] += require_parts[current] * parts_cnt; // 필요한 부품수를 부품 번호에 저장
			if (--degree[parts_idx] == 0)
				q.push(parts_idx);
		}
	}

	sort(nomal_parts.begin(), nomal_parts.end());

	for (int i = 0; i < nomal_parts.size(); i++) {
		cout << nomal_parts[i] << " " << require_parts[nomal_parts[i]]<<"\n";
	}
}

int main(void) {
	Input();
	solution();
}

아이디어

완제품을 조립하기 위해 필요한 부품의 개수를 구하는 문제인데 부품은 기본부품과 중간 부품으로 나뉘고 기본부품만 출력 해야함

기본 부품으로 조합된 중간 부품의 개수를 체크하여 기본부품의 개수를 변화시키는 방법을 생각하기 힘들었음

위상정렬 기본식인 진입차수가 0인 노드부터 공략하는게 아닌 완제품부터 기본부품까지 위상정렬을 해나가는게 포인트

조립시 필요한 부품개수 x 현재 필요한 부품의 필요한 개수 다음 부품의 개수에 넣어주면 됨