[PS] 백준 2637번: 장난감조립

|

문제

내가 이해한 문제 내용

장난감 완제품을 만드는데 사용하는 부품은 기본 부품과 중간 부품으로 나뉜다. 또한 중간 부품은 기본 부품 또는 중간 부품으로 만들 수 있다. 이 때, 완제품을 만드는데 필요한 기본부품의 각 개수를 출력하시오.

접근 방식

처음에 단순 for문으로 접근했다가 나중에서야 DFS를 통해 해결할 수 있다는 것을 알았다.

어려웠던 점 & 배운 점

이런 문제는 빠르게 풀어야 하는데 고민을 좀 오래 한 것 같아 아쉽다. 어려웠던 점은 기본 부품의 각 개수를 가지고 있어야 한다는 점을 DFS로 구현하는 것이다. 단순 DFS라면 값만 리턴하면 되지만 이 경우엔 따로 각 부품에 대해서 DFS를 돌려야 했고 저장도 해줘야 했다.

시간복잡도

DFS를 최대 $V-1$번 하기 때문에 $O(V*(V+E))$

코드

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

typedef pair<int,int> pii;

vector<pii> g[101];
int n,m,_x,_y,k;
int dp[101][101];
int visit[101];

int dfs(int v, int res)
{
    if(g[v].size()) visit[v] = 1;

    for(int i=0; i<g[v].size(); i++){
        int next = g[v][i].first;
        int num = g[v][i].second;

        if(g[next].size()){
            dp[v][res] += (visit[next] ? dp[next][res] : dfs(next,res)) * num;
        }
    }
    return dp[v][res];
}

int main(void)
{
    scanf("%d%d",&n,&m);

    for(int i=0; i<m; i++){
        scanf("%d%d%d",&_x,&_y,&k);
        g[_x].push_back({_y,k});
        dp[_x][_y] = k;
    }

    for(int i=1; i<n; i++){
        if(!g[i].size()){
            printf("%d %d\n", i, dfs(n,i));
            memset(visit,0,sizeof(visit));
        }
    }

    return 0;
}