C++ / 백준 / 2637 / 장난감 조립

문제

 

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

2637번: 장난감 조립

 

문제풀이

 

다른 사람들의 풀이보다 벡터를 더 선언한 것 같다..

입력값들을 저장하는 input,

Y 부품을 만들기 위해 필요한 X의 개수를 저장하는 ingr 벡터, ingr[Y][X]=K;

기본 부품인지 나타내는 bool형 벡터 isBase,

들어오는 간선의 개수를 알려주는 indegree 벡터를 선언했다.

 

	for (int idx = 0; idx < M; ++idx) {
		cin >> X >> Y >> K;
		input[Y].push_back({ X,K });
		++indegree[X];
	}
	for (int idx = 1; idx < N; ++idx) {
		if (indegree[idx] == 0) {
			q.push(idx);
			isBase[idx] = true;
		}
	}

X를 만드는데 Y부품이 K개 필요하다는 입력이 들어온다.

위상정렬을 이용해 문제를 해결할 것이므로 input에는 재료인 Y에 완성품인 X와 K를 저장한다.

입력이 끝났으면 indegree값이 0인 부품을 찾는다.

이 부품들은 모두 기본 부품이라는 의미이다.

 

 

void topology_sort() {
	for (int i = 1; i <= N; ++i) {
		int num = q.front();
		q.pop();
		for (int idx = 0; idx < input[num].size(); ++idx) {
			int next = input[num][idx].first;
			int cnt = input[num][idx].second;
			if (isBase[num] == true) {
				ingr[next][num] += cnt;
			}
			else {
				for (auto iter = ingr[num].begin(); iter != ingr[num].end(); ++iter) {
					ingr[next][iter->first] += (iter->second * cnt);
				}
			}
			--indegree[next];
			if (indegree[next] == 0) q.push(next);
		}
	}
}

위상정렬 코드이다.

num은 입력에서 Y에 해당하고, next는 X에 해당하는 부품이다.

만약 num이 기본부품이면 ingr[next][num]에 cnt개수만큼 더한다.

기본 부품이 아니라면 ingr[num]에는 num을 만들기 위해 필요한 기본 부품들의 번호와 개수가 입력되어 있으므로 for문을 통해 모든 기본 부품들의 개수를 ingr[next]에 저장해 준다.

(예를 들어 5를 만드는데 1이 2개 필요하고, 7을 만드는데 5가 2개 필요하다고 가정하자,

부품1 * 2 -> 부품5, 부품5 * 2 -> 부품7 이런 식으로 표현할 수 있다.

부품 7을 만들기 위해서는 기본 부품 1이 총 4개가 필요하다)

 

그다음은 --indegree[next]을 하고 값이 0이 된다면 큐에 push 한다.

위 topology_sort 함수가 종료되면 반복문을 통해 ingr[완성품]의 기본 부품 개수들을 모두 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

vector<map<int, int>>ingr;
vector<vector<pii>>input;
vector<bool>isBase;
vector<int>indegree;
queue<int>q;
int N;

void topology_sort() {
	for (int i = 1; i <= N; ++i) {
		int num = q.front();
		q.pop();
		for (int idx = 0; idx < input[num].size(); ++idx) {
			int next = input[num][idx].first;
			int cnt = input[num][idx].second;
			if (isBase[num] == true) {
				ingr[next][num] += cnt;
			}
			else {
				for (auto iter = ingr[num].begin(); iter != ingr[num].end(); ++iter) {
					ingr[next][iter->first] += (iter->second * cnt);
				}
			}
			--indegree[next];
			if (indegree[next] == 0) q.push(next);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int M(0);
	cin >> N >> M;
	isBase = vector<bool>(N + 1, false);
	ingr = vector<map<int, int>>(N + 1);
	input = vector<vector<pii>>(N + 1);
	indegree = vector<int>(N + 1, 0);

	int X(0), Y(0), K(0);

	for (int idx = 0; idx < M; ++idx) {
		cin >> X >> Y >> K;
		input[Y].push_back({ X,K });
		++indegree[X];
	}
	for (int idx = 1; idx < N; ++idx) {
		if (indegree[idx] == 0) {
			q.push(idx);
			isBase[idx] = true;
		}
	}

	topology_sort();

	for (auto iter = ingr[N].begin(); iter != ingr[N].end(); ++iter) {
		cout << iter->first << " " << iter->second << '\n';
	}
}