[2637번] 장난감조립

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상 정렬(Topological Sort) :: http://http;//www.crocus.co.kr/716

이 문제는 단순 dfs로 풀어도 풀리는 문제이지만, 알고리즘 분류상 위상 정렬로 해결해보라는 의미를 가지고 있으므로

이 문제를 위상 정렬을 접목하여 해결해 본다.

이 문제는 기본 부품, 중간 부품, 완성품으로 나뉘는데 완성품으로 가기까지 중간 부품의 기본 부품을 계속해서 업데이트 해주는 것이 중요하다.

만약 1->2->3이고 1->2가 2, 2->3이 3이면

2는 기본 부품 1을 2개로 가지고 있게되고, 3은 중간 부품 3를 가지고 있지만, 2의 정보를 이용하여 

2가 몇개 필요한지 * 2에서 기본 부품 1이 몇개 필요한지로 3에서의 기본 부품 1에 대한 정보를 업데이트한다.

따라서 2가 3개 필요하고 2에서 기본 부품 1은 2개 필요하니 

3 * 2 = 6으로 3에서의 기본 부품 1의 값을 6으로 업데이트 해준다.

그렇게 순차적으로 최종 부품까지 따라 올라가면 정답을 찾을 수 있다.

자세한 내용은 주석을 통해 달아두었다.

소스 코드 : 

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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

#include <iostream> #include <cstdio> #include <queue>   #define MAX_NODE 101   using namespace std;   int line[MAX_NODE]; // chk[x][y] = k :: x부품을 만들기 위해 y를 k개 이용하는 의미 int chk[MAX_NODE][MAX_NODE]; int root[MAX_NODE];   vector<int> vc[MAX_NODE];   int main() {     int v, e;       scanf("%d %d", &v, &e);       // 입력 부분     // chk는 prev->cur이 존재한다면 간선의 값      for (int i = 0; i < e; i++)     {         int cur, prev, val;         scanf("%d %d %d", &cur, &prev, &val);           line[cur]++;         vc[prev].push_back(cur);           chk[cur][prev] = val;     }       queue<int> q;       // i에 들어오는 간선이 없다면 기본 부품이고, push     for (int i = 1; i <= v; i++)         if (line[i] == 0)         {             root[i] = 1;             q.push(i);         }       for (int i = 0; i < v; i++)     {         int cur = q.front();         q.pop();           // cur->next에 해당하는 간선정보 추가         for (int j = 0; j < vc[cur].size(); j++)         {             int next = vc[cur][j];               // 들어오는 간선이 없다면             if (--line[next] == 0)             {                 // 이제 들어왔던 간선들에 대해서 값을 계산해준다.                 for (int here = 1; here <= v; here++)                 {                     if (root[here] == 1)                         continue;                                          // 곱할 수(만약 9->12가 3이면 9의 기본 부품 정보에 *3을 하여 12에 더해준다.)                     int mul = chk[next][here];                       for (int there = 1; there <= v; there++)                     {                         // here을 조립하는데 there이 존재한다면                         if (chk[here][there])                         {                             // next를 조립하는데 there로 갱신                             if (root[there] == 1)                                 chk[next][there] += (chk[here][there] * mul);                         }                     }                                      }                                  q.push(next);             }         }     }       // 출력     for (int i = 1; i <= v; i++)         if(root[i] == 1)             printf("%d %d\n", i, chk[v][i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus