[Leetcode] 310. Minimum Height Trees (C++)

문제

310. Minimum Height Trees

코드

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 0) return {};
        if (n == 1) return {0};
        
        vector<int>res, degrees(n,0);
        vector<vector<int>>adj(n);
        for(int i=0; i < edges.size(); i++) {
            adj[edges[i][0]].push_back(edges[i][1]);
            adj[edges[i][1]].push_back(edges[i][0]);
            degrees[edges[i][1]]++;
            degrees[edges[i][0]]++;
        }
        queue<int>queue;
        for(int i=0;i<n;i++){
            if (degrees[i] == 1) queue.push(i);
        }
        while(!queue.empty()) {
            res.clear();
            int size=queue.size();
            for(int i=0;i<size;i++) {
                int cur=queue.front();
                queue.pop();
                res.push_back(cur);
                for(auto &neighbor:adj[cur]) {
                    degrees[neighbor]--;
                    if(degrees[neighbor]==1)
                        queue.push(neighbor);
                }
            }
        }
        return res;
    }
};

접근

MHT의 루트를 찾는다는 것은 결국 가장 긴 길이의 경로의 중간 노드를 찾는 것과 마찬가지다. 이를 찾기 위해 직접 만들면서 찾는 것이 아닌 간선이 하나밖에 없는 leaf node들을 제거해나가면서 가운데에 위치한 노드를 찾을 수가 있었다. degrees에 해당 노드와 연결된 노드의 수를 저장하고 queue에 leaf node 들을 넣고 해당 연결을 끊어나가면서 최종적으로 남는 노드들을 찾는 것이다. 만약 제일 긴 경로에 속한 노드의 수가 홀수라면 가운데의 한 노드만이 결과가 될 것이고, 짝수라면 두 개의 노드가 결과로 나올 것이다.