백준 2637 c++ "장난감 조립" -[PlusUltraCode]

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

2637번: 장난감 조립

[필자 사고]

이 문제는 위상정렬 알고리즘을 사용하여 풀 수있는 문제이다.

 

이 문제의 특이한 점은 dist 카운트를 2번 사용하여 기본 부품의 갯수와 위상정렬에 사용해야 하는 dist총 2번을 저장해야 된다. 

 

또한 위상정렬의 대표 문제들은 dist==0일때 마다 특별한 이벤트가 발생했지만 이번 문제는 dist==0이 아닐 때에도 pathLoad에 값을 갱신해줘야 한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
typedef pair<int, int> Node;

vector<vector<Node>> Arr;

vector<int> pathLoad;
vector<int> dist;
vector<int> Find_gibon;



void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	pathLoad.resize(N + 1,0);
	Find_gibon.resize(N + 1, 0);
	dist.resize(N + 1,0);
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Arr[s].push_back({ w,e });
		dist[e]++;
		Find_gibon[s]++;
	}
	
}

void Topolgical_Sort() {
	queue<int> myQueue;
	pathLoad[N] = 1;
	for (int i = 1; i <= N; i++) {
		if (dist[i] == 0) {
			myQueue.push(i);
		}
	}
	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		myQueue.pop();
		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextCost = nextNode.first;
			dist[nextIdx]--;
			pathLoad[nextIdx] += pathLoad[nowIdx] * nextCost;
			if (dist[nextIdx] == 0) {
				
				myQueue.push(nextIdx);
			}
		}
	}
}



int main(void) {
	Input();
	Topolgical_Sort();
	vector<int> Tank;
	for (int i = 1; i <= N; i++) {
		if (Find_gibon[i] == 0) {
			cout << i << " ";
			cout << pathLoad[i] << "\n";
		}
	}
	
}