https://www.acmicpc.net/problem/2637
2637번: 장난감 조립
첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/72
[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)
1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방
rudalsd.tistory.com
1. 완제품에서부터 부품 쪽으로 내려가면서 개수를 저장해야 하므로, X -> Y 방향으로 단방향 그래프를 만들어줍니다.
2. 1과 동시에 중간 부품이 몇 번 필요한지 in [ Y ]++를 통해 저장해 주고, basic [ X ] = 1을 통해 기초 부품인지 아닌지 체크해 줍니다.
3. 위상정렬을 통해 N번부터 ans 배열에 필요한 부품의 개수를 저장합니다.
4. 하위 부품의 개수는 ans [next] += ans [cur] * next.cnt로 저장합니다.
5. basic [ i ] != 1인 부품에 대해서 ans [ i ]를 출력해 줍니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<iostream> #include<vector> #include<queue> using namespace std; int N, M; vector<pair<int, int>> list[101]; int ans[101]; int basic[101]; int in[101]; int main() { scanf("%d %d", &N, &M); for (int i = 0; i < M; i++) { int X, Y, K; scanf("%d %d %d", &X, &Y, &K); list[X].push_back({ Y,K }); basic[X] = 1; in[Y]++; } queue<int> q; q.push(N); ans[N] = 1; while (!q.empty()) { const int cur = q.front(); q.pop(); for (auto& next : list[cur]) { ans[next.first] += ans[cur] * next.second; in[next.first]--; if (in[next.first] == 0) { q.push(next.first); } } } for (int i = 1; i <= N; i++) { if (basic[i] != 1) { printf("%d %d\n", i, ans[i]); } } } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 17836번 - 공주님을 구해라! (C++) (0) | 2023.02.11 |
|---|---|
| [ 백준 ] 15971번 - 두 로봇 (C++) (0) | 2023.02.10 |
| [ 백준 ] 11658번 - 구간 합 구하기 3 (C++) (0) | 2023.02.08 |
| [ 백준 ] 2458번 - 키 순서 (C++) (0) | 2023.02.07 |
| [ 백준 ] 2211번 - 네트워크 복구 (C++) (0) | 2023.02.06 |