[LeetCode] 310. Minimum Height Trees

https://leetcode.com/problems/minimum-height-trees/description/

Leetcode - Minimum Height Trees

문제 유형 : bfs / 위상 정렬

문제 난이도 : Medium

 

문제

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h))  are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

 

트리는 두 개의 정점이 서로 한 길로만 이어져 있는, 즉, 사이클이 없는 그래프입니다.

 

n개의 노드가 0~n-1의 라벨로 붙어있습니다. 연결 정보 배열 edges[i] = [ai, bi]는 ai에서 bi로의 연결이 있다는 뜻입니다.

당신은 어느 노드든 루트로 정할 수 있습니다.

최소 높이의 트리를 만들려고 합니다. 높이란 가장 깊은 노드에서 루트까지의 이동 수를 말합니다.

루트로 가능한 모든 루트의 라벨을 반환하시오.

 

풀이

위상 정렬을 통해서 해결할 수 있다.

본인은 위상정렬 문제를 너무 오랜만에 봐서, 처음에는 생각을 깊게 하다가, 브루트 포스로 모든 노드를 루트로 잡는 무식한 방법으로 시작했으나, 루트에서부터 시작하는 아이디어를 떠올려서 위상 정렬이 있었음을 기억했다.

 

위상 정렬로 연결 수가 1인 노드들을 큐에 장전하고 탐색을 시작하자.

다음 노드의 차수를 1씩 낮춘다.

차수가 1이 되면(루트 방향으로 하나만 남으면), 그 노드도 큐에 넣어준다.

 

그러나 이 알고리즘으로는 계층 구분만 가능한데, 루트를 찾으려면, 매번 루트를 갱신해야 한다.

큐의 요소들을 빼면서, 루트들 중 하나라고 가정하고 정답 배열에 넣어두는 것이다.

새 반복문이 시작되면 초기화하고, 탈출하면 마지막으로 탐색한 계층의 노드들이 남아있는데, 그 노드들이 루트가 될 수 있는 노드들이다.

 

코드

C++

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return {0};
        vector<vector<int>> graph(n);
        vector<bool> visited(n, 0);
        vector<int> indegree(n, 0);
        vector<int> ans;

        for(const auto &edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            indegree[edge[0]]++;
            indegree[edge[1]]++;
        }

        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(indegree[i] == 1) {
                q.push(i);
                visited[i] = true;
            }
        }

        while(!q.empty()) {
            int qsize = q.size();
            ans = {};

            for(int i = 0; i < qsize; i++) {
                auto curr = q.front();
                q.pop();
                ans.push_back(curr);

                for(const auto &next : graph[curr]) {
                    if(!visited[next]) {
                        indegree[next]--;
                        if(indegree[next] <= 1) {
                            q.push(next);
                            visited[next] = true;
                        }
                    }
                }
            }
        }

        return ans;
    }
};