https://www.acmicpc.net/problem/2637
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
typedef pair<int, int> pi;
int n,m;
int main() {
FASTIO;
cin >> n >> m;
vector<int>depth(n + 1, 0);
vector<vector<pi>> p(n+1);
vector<vector<int>> cnt(n + 1, vector<int>(n + 1, 0));
for (int i = 0,x, y, k; i < m; i++) {
cin >> x >> y >> k;
depth[x]++;
p[y].push_back({ x,k });
}
queue<int> q;
for (int i = 1; i <= n; i++)
if (depth[i] == 0) {
q.push(i);
cnt[i][i] = 1;
}
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < p[now].size(); i++) {
int next = p[now][i].first;
int need = p[now][i].second;
for (int j = 1; j <=n; j++) {
if (cnt[now][j] != 0)
cnt[next][j] += cnt[now][j] * need;
}
depth[next]--;
if (depth[next] == 0)
q.push(next);
}
}
for (int i = 1; i < n; i++)
if (cnt[n][i] > 0)
cout << i << " " << cnt[n][i] << "\n";
return 0;
}
설명
필요한 변수를 입력받습니다. 부품들 간의 관계 X, Y, K는 X를 만드는 데 Y가 K개 필요하다는 의미이므로 depth[X]를 1 증가시켜 필요한 부품의 종류를 세어줍니다. 그리고 P[Y].push_back({X, K})로 Y는 추후 X를 만들기 위해 K개 필요함을 기록합니다.
depth[i] == 0 이라면 해당 부품을 만들기 위해서 필요한 다른 부품이 없다는 의미입니다. 따라서 cnt[i][i]를 1로 저장해주고 위상정렬을 위한 큐에 i를 넣어줍니다. 이때 cnt[i][j]는 i 부품을 만들기 위해 필요한 j 부품의 개수입니다.
이제 위상정렬을 진행합니다. p[now]에는 Y가 k개 필요한 부품 X의 정보가 들어있습니다. 따라서 매번 cnt[now][j]가 0이 아닌 값에 대해서 cnt[next][j] += cnt[now][j] * k 로 갱신합니다. 이렇게 하면 next 부품을 만들기 위해 필요한 선수 부품 한 종류에 대한 처리가 끝났으니 depth를 1 감소시켜줍니다. 0이 되었다면 이제 해당 부품 번호를 큐에 넣습니다.
위상정렬 이후 cnt[n][i]가 양수인 경우에만 주어진 형식대로 출력하고 프로그램을 종료합니다.
느낀 점
부품 사이 선수관계가 있기 때문에 위상정렬로 문제를 해결했습니다! 처음에 정보 관리를 잘못 생각해서 코드를 작성하는 과정이 오래 걸렸습니다.
'PS (C, C++)' 카테고리의 다른 글
[백준/C++] 2234 성곽 (0) | 2024.10.01 |
---|---|
[백준/C++] 14382 숫자세는 양 (Large) (1) | 2024.09.25 |
[백준/C++] 24392 영재와 징검다리 (0) | 2024.09.23 |
[백준/C++] 14231 박스 포장 (0) | 2024.09.23 |
[백준/C++] 21555 빛의 돌 옮기기 (0) | 2024.09.19 |