[백준OJ] 2637번 장난감 조립

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

2637번: 장난감 조립

---

 

-풀이-

위상정렬을 이용하였다.

parts[i][j]=k 라고 할때, 이 의미는 j번 부품을 만들기 위해서 필요한 i의 개수를 k개라고 하자.

 

현재 정점에서 필요한 블록들의 개수는, 현재 정점으로 진입하는 정점들의 각각의 블록들마다 cost를 곱해준 값과 같다.

기본 파츠들은 자신의 파츠만 1개 가지고 있다. 예를들어 중간부품5가 기본부품 1을 2개, 2를 2개 가지고 있다면,

parts[1][5]=2;

parts[2][5]=2;

parts[3][5]=0;

parts[4][5]=0;

.....

parts[9][5]=0;

이 된다.

 

이떄, 중간부품 6이 중간부품 5가 2개 필요하다고 한다면, 5에 있는 parts들을 각각 2씩 곱해서 더해준뒤, 현재 가지고 있는 파츠에 더해주면된다.

parts[1][6]=parts[1][5]*2+parts[1][6]=4+0=4;

parts[2][6]=parts[2][5]*2+parts[2][6]=4+0=4;

parts[3][6]=parts[3][5]*2+parts[3][6]=0+0=0;

parts[4][6]=parts[4][5]*2+parts[4][6]=0+0=0;

....

parts[9][6]=parts[9][5]*2+parts[9][6]=0+0=0;

 

이 로직을 위상정렬한 순서대로 실행해주면, 맨 마지막 N번은 기본부품들이 몇개씩 필요한지 구할 수 있게된다.

 

-코드-

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

vector<pair<int,int>> maze[101];
int parts[101][101]={0};
int indeg[101]={0};
int n,m,x,y,k;

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>x>>y>>k;
        maze[y].push_back({x,k});
        indeg[x]++;
    }
    
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!indeg[i]){
            q.push(i);
            parts[i][i]=1;
        }
    }
    
    while(!q.empty()){
        int now=q.front();
        q.pop();
        
        for(pair<int,int> t:maze[now]){
            int next=t.first;
            int cost=t.second;
            
            indeg[next]--;
            if(!indeg[next]) q.push(next);    
            
            for(int i=1;i<=n;i++){
                parts[i][next]+=parts[i][now]*cost;
            }
        
        }
    }
    
    for(int i=1;i<=n;i++){
        if(parts[i][n]){
            cout<<i<< " " <<parts[i][n]<<"\n";
        }
    }
}

//