백준 2637 - 장난감 조립(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2637

2637번: 장난감 조립

위상 정렬을 역방향으로 이용하는 문제입니다.

기본 부품, 중간 부품, 완제품이 존재합니다.
중간 부품과 완제품을 만들기 위한 부품 번호와 갯수가 주어질 때, 완제품을 만들 경우 몇 개의 기본 부품이 사용되는지를 구하는 문제입니다.

문제에서 주어진 예시를 확인해보겠습니다.(입력에서 1,2,3,4 -> 기본 부품 / 5, 6 -> 중간 부품 / 7 -> 완제품임을 알 수 있습니다.)
7번 완제품을 만들기 위해서는 4번 5개, 5번 2개, 6번 3개가 필요합니다.
5번 중간 부품을 만들기 위해서는 1번 2개, 2번 2개가 필요합니다.
6번 중간 부품을 만들기 위해서는 3번 3개, 4번 4개, 5번 2개가 필요합니다.

따라서,
7번 -> 4번 * 5
           5번 * 2 -> 1번 * 4
                             2번 * 4
           6번 * 3 -> 3번 * 9
                             4번 * 12
                             5번 * 6 -> 1번 * 12
                                                2번 * 12
-> 1번 16개, 2번 16개, 3번 9개, 4번 12개가 필요함을 알 수 있습니다.

해당 방식처럼 완제품에서 기본 부품으로 내려가는 방법을 취한다면, 답을 구할 수 있음을 알 수 있습니다.

따라서, 입력으로 X, Y, K가 주어진다면
vector[X]에 Y를 집어넣는 방식을 통해 연결을 해주고, Y의 단계를 1을 증가해 X의 다음 단계임을 저장해줍니다.
또한, X를 만들기 위한 Y의 갯수도 알아야하니 100*100의 2차원 배열을 만들어 [X][Y] = K를 저장해줍니다.

탐색은 완제품에서 시작해서(어떤 밑 단계의 부품이 사용되는지 + 다음 탐색한 밑 단계는 어떤 것인지)를 확인하게 될 것입니다.
이때, 해당 부품이 몇개 사용되었는지를 저장해주면 됩니다.
몇개 사용되는지 확인하는 방법은 간단합니다.
이전에 저장한 [X][Y]의 값과 현재 사용된 윗 단계의 부품 갯수를 곱해주면 됩니다.
->relation[X][Y] * use[X] 가 됩니다.

이를 전부 구했다면, 마지막으로 기본 부품을 찾아서 몇개 사용되었는지를 출력해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;

int N, M;
int relation[101][101]; // X를 만들기 위해 Y가 몇개가 필요한지
vector<int> connect[101]; // 어느 부품들이 연결되어 있는지
int step[101]; // X 부품을 만들기 위해 거쳐야 하는 부품 종류의 수
int use[101]; // X 부품을 몇개 사용했는지
int base[101]; // 기초 부품
queue<int> q;



void topological_sorting(){
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i];
			// 상위 단계의 부품이 사용된 개수와 (X, XX)부품 간의 필요한 부품수를 곱하면 하위 단계의 부품이 몇 개 사용되는지를 구할 수 있다.
			use[xx] += relation[x][xx] * use[x]; 
			step[xx]--; // 단계를 하나 빼, 조건 하나가 사용됨을 표현한다.
			if(step[xx] == 0) q.push(xx); // 단계가 0이 되면, 큐에 넣어 하위 단계 부품이 사용될 떄를 확인한다.
		}
	}
}

void solve(){
	for(int i = 1; i <= N; i++){
		if(step[i] == 0){ // 완제품을 찾는다.
			q.push(i);
			use[i]++;
		}
	}
	topological_sorting();
	for(int i = 1; i <= N; i++){ // 기초 부품을 찾은 뒤, 몇개 사용되었는지를 출력한다.
		if(base[i] == 0) cout << i << " " << use[i] << "\n";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	cin >> M;
	for(int i = 1; i <= M; i++){
		int x, y, k;
		cin >> x >> y >> k;
		connect[x].push_back(y); //기초 부품을 사용한 횟수니 완제품에서 내려가는 형식을 취한다.
		relation[x][y] = k; // x부품을 만들기 위해서 y부품이 몇개 사용됐는지를 저장한다.
		step[y]++;
		base[x]++; // 기초부품를 찾는다.
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.