백준/그래프
백준 2637 c++ "장난감 조립" -[PlusUltraCode]
PlusUltraCode
2024. 3. 2. 15:39
https://www.acmicpc.net/problem/2637
2637번: 장난감 조립
첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주
www.acmicpc.net
[필자 사고]
이 문제는 위상정렬 알고리즘을 사용하여 풀 수있는 문제이다.
이 문제의 특이한 점은 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";
}
}
}