[Algorithm]Baekjoon 2637번 : 장난감 조립

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

2637번: 장난감 조립

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
bool visited[101] = { false };
vector<vector<pair<int, int>>> graph(101);
vector<unordered_map<int, int>> primaryPartsInfo(101);
 
 
void DFS(int curPartsNum)
{
    for (int i = 0; i < graph[curPartsNum].size(); ++i)
    {
        int nextNode = graph[curPartsNum][i].first;
        int count = graph[curPartsNum][i].second;
 
        if (graph[nextNode].size() == 0) // 기본부품이면
        { 
            primaryPartsInfo[curPartsNum][nextNode] += count;
            continue;
        }
 
        if (!visited[nextNode])
        {
            visited[nextNode] = true;
            DFS(nextNode);
        }
 
        for (auto iter = primaryPartsInfo[nextNode].begin(); iter != primaryPartsInfo[nextNode].end(); iter++)
        {
            int primaryPartsNum = iter->first;
            int primaryPartsCount = iter->second;
 
            primaryPartsInfo[curPartsNum][primaryPartsNum] += primaryPartsCount * count;
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int x, y, k;
 
        cin >> x >> y >> k;
 
        graph[x].push_back({ y,k });
    }
 
    visited[n] = true;
    DFS(n);
 
    vector<pair<int, int>> answer;
 
    for (auto iter = primaryPartsInfo[n].begin(); iter != primaryPartsInfo[n].end(); iter++)
    {
        answer.push_back({ iter->first, iter->second });
    }
 
    sort(answer.begin(), answer.end());
 
    for (int i = 0; i < answer.size(); ++i)
    {
        printf("%d %d\n", answer[i].first, answer[i].second);
    }
}

 

골드2짜리긴한데 생각보다 어렵지 않은 문제다.

각 부품관계가 얽혀있는데, 최종 완제품을 만들었을 때 기본부품의 개수를 구하는 문제이다.

중간부품을 구성하는 기본부품의 개수를 구하는부분이 중복되기 때문에 해당부분만 처리해주면 되는 문제이다.

 

나같은경우, vector<unordered_map<int,int>> 라는 컨테이너를 따로 만들어서, iterator를 통해 특정부품의 기본부품들의 개수를 바로 알 수 있게 사용해봤다.

맵을사용안하면 최대 n개의 배열탐색을 해야하는데, n값이 최대 100밖에 안되기때문에 배열을 사용하더라도 통과가 되긴했을것이다.

 

dfs로 자식노드들을 탐색시도할건데, 이전에 구해놨던 값이면 해당 자식노드를 구성하는 기본부품의 개수를 전부 자신한테 업데이트 한다.

구해놨던게 아니면 방문표시하고 DFS를 호출해서 값을 구해놓은다음, 자신한테 업데이트하면 된다.