[백준] 2637 장난감조립

위상정렬로 풀 수 있는 문제다

장난감 n을 만드는 기본장난감 수를 다 찾으면 된다

그럼 그래프를 만들고 어떠한 장난감을 만들기 위한 장난감이 몇개인지 

다 더해나가면 된다

d[i][j] => i를 만들기 위한 장난감 j의 수

여기에 다 더해나가면 d[n][k]에 n을 만들기 위한 k의수가 저장된다~!

근데 처음에 이걸 위상정렬 끝내고 밖에서 처리했는데 숫자가

조금씩 차이나며 틀렸다

 

그래서 위상정렬 하면서 같이 처리하니까 맞더라.. ㅎ

작은 오류를 못잡은 것 같다ㅎㅎ

쓸데없는 코딩은 안하는게 좋은 것 같다.

짧게 간결하게 끝내야지~~!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int d[111][111],ind[111],n,m;
bool check[111];
vector<vector<pair<int, int>>> Graph;
 
int main() {
    scanf(" %d %d", &n, &m);
    Graph.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf(" %d %d %d", &u, &v, &w);
        Graph[v].push_back({ u,w });
        ind[u] += 1;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!ind[i]) {
            check[i] = true;
            q.push(i);
            d[i][i] = 1;
        }
    }
 
    while (!q.empty()) {
        int here = q.front();
        q.pop();
 
        for (int i = 0; i < Graph[here].size(); i++) {
            int next = Graph[here][i].first;
            int cost = Graph[here][i].second;
            for (int j = 1; j <= n; j++) d[next][j] += d[here][j] * cost;
            ind[next]--;
 
            if (ind[next] == 0) q.push(next);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (check[i]) {
            printf("%d %d\n", i, d[n][i]);
        }
    }
}