[C++] 해커랭크 Cut the Tree

int cutTheTree(const vector<int>& data, const vector<vector<int>>& edges)
{
    vector<vector<int>> nodes(data.size());
    vector<int> sumData = data;
    stack<pair<int,int>> stackNodes;
    int result = 0;

    //save nodes
    for (int i = 0; i < edges.size(); ++i)
    {
        nodes[edges[i][0] - 1].push_back(edges[i][1] - 1);
        nodes[edges[i][1] - 1].push_back(edges[i][0] - 1);
    }

    //save stack (BFS)
    {
        vector<bool> visited(data.size(), false);
        queue<int> q;
        q.push(0);

        while (!q.empty())
        {
            int currNode = q.front();
            q.pop();

            visited[currNode] = true;

            for (int j = 0; j < nodes[currNode].size(); ++j)
            {
                int nextNode = nodes[currNode][j];

                if (visited[nextNode] == false)
                {
                    stackNodes.push({ currNode, nextNode });
                    q.push(nextNode);
                }
            }
        }
    }
    
    //sum node
    while (!stackNodes.empty())
    {
        int leftNode = stackNodes.top().first;
        int rightNode = stackNodes.top().second;
        stackNodes.pop();

        sumData[leftNode] += sumData[rightNode];
    }

    if (sumData.size() > 0)
    {
        result = sumData[0] + 1;
    }

    //find min
    for (int i = 1; i < sumData.size(); ++i)
    {
        int tree1 = sumData[0] - sumData[i];
        int tree2 = sumData[i];

        result = min(result, abs(tree1 - tree2));
    }

    return result;
}

 

요약

끝 지점부터 출발 지점까지 되돌아가면서 노드의 합을 저장해놓고, 최적의 트리 나누기를 구한다.

 

풀이

1. 출발 지점부터 끝 지점까지 순회하며 되돌아 올 길을 만들어 놓는다.

2. 되돌아오면서 합을 더해준다.

3. data에 저장된 노드들의 모든 합 - 현재 더해진 노드(하나의 트리)는 반대 트리 값이다.

4. 두 개의 트리를 다시 빼면 각 트리간의 격차가 나온다.

 

 

https://www.hackerrank.com/challenges/cut-the-tree/problem

Cut the Tree | HackerRank