BOJ 2637 장난감 조립

사용한 알고리즘

위상정렬, DP

알고리즘 설명

i번째 부품을 만들기 위해서는 j부품이 k개 필요하다고 하자.
이를 j->i, 가중치가 K인 그래프로 표현할 수 있다.
또한 indegree의 개수를 기입하는데, indegree가 없는 것이 기초 부품이다.
기초 부품들로 부터 시작하여 위상정렬로 가충치 만큼 자신의 부품을 더해준다.
위에 필요한 부품들을 dp(i,j)어레이에 정의한다.
dp(i,j)는 i번째 부품을 만들기 위해서 필요한 j번째 부품 개수인 DP 형태로 정의한다.
위상정렬 후 dp(N,i):(0 <= i < N) 를 출력한다.

풀이

// baekjoon 2637 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
const int MAX_N=100;

int N, M;
int dp[MAX_N][MAX_N];
int indeg[MAX_N];
vector<int> adj[MAX_N];

int main() {
  scanf("%d", &N);
  scanf("%d", &M);
  // 초기 그래프 관계 정의
  while (M--) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--, v--;
    dp[u][v] = w;
    indeg[u]++;
    adj[v].push_back(u);
  }
  // 기초 부품들을 큐의 push함
  queue<int> q;
  for (int i=0; i<N; i++) {
    if (!indeg[i]) {
      q.push(i);
      dp[i][i] = 1;
    }
  }

  // 위상정렬 알고리즘
  for (int i=0; i<N; i++) {
    int cur = q.front();
    q.pop();
    for (int j=0; j<adj[cur].size(); j++) {
      int num = dp[adj[cur][j]][cur];
      dp[adj[cur][j]][cur] = 0;
      // 기초 부품을 num(가중치) 만큼 곱하여 정렬 시킨다.
      for (int k=0; k<N; k++) {
        dp[adj[cur][j]][k] += num * dp[cur][k];
      }
      // 더 이상 업데이트할 부품이 없으면 Queue에 추가한다.
      if (--indeg[adj[cur][j]] == 0) {
        q.push(adj[cur][j]);
      }
    }
  }

  // 결과 출력
  for (int i=0; i<N-1; i++)
    if (dp[N-1][i])
      printf("%d %d\n", i+1, dp[N-1][i]);

  return 0;
}