Number of Nodes in the Sub-Tree With the Same Label

트리 노드 개수 n과 노드 간의 연결이 담긴 2차원 정수 벡터,

그리고 노드 인덱스 기준으로 노드별 레이블(알파벳 문자 하나)을 써놓은 문자열 하나를 받는다.

문제는 노드마다 자기 자신을 포함하여 자신과 같은 레이블을 가진 자식 노드들을 찾고,

몇 개인지 파악하여 정수형 벡터에 인덱스 기준 노드별로 개수를 써서 반환해야 한다.

class Solution {
public:
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        
        vector<int> result(n);

        vector<vector<int>> graph(n);
        int length = edges.size();
        for (int i = 0; i < length ; i++)
        {
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
        }

        vector<bool> visited(n);
        visited[0] = true;

        SearchDFS(0, graph, visited, labels, result);

        return result;
    }

    vector<int> SearchDFS(int n, vector<vector<int>> &graph, vector<bool> &visited, string &labels, vector<int> &result)
    {
        int length = graph[n].size();
        vector<int> sum(26, 0);

        for (int i = 0; i < length; i++)
        {
            if (visited[graph[n][i]])
            {
                continue;
            }

            visited[graph[n][i]] = true;

            vector<int> temp = SearchDFS(graph[n][i] , graph, visited, labels, result);
            for (int j = 0; j < 26; j++)
            {
                sum[j] += temp[j];
            }

            visited[graph[n][i]] = false;

        }

        sum[labels[n] - 'a']++;
        result[n] = sum[labels[n] - 'a'];

        return sum;
    }

};