<Medium> Minimum Height Trees (LeetCode : C#)

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

📕 문제 설명

노드 개수 n이 주어지고 edge정보가 주어질 때 최소 신장 트리의 root 반환하기

edges[i] = [a_i, b_i]

• Input
  노드 개수 n, edge 정보 (int[][])
• Output
  최소 신장 트리 root 반환

예제

풀이

최소 높이를 구성하기 위해서는 가장 연결이 많은 노드를 루트로 잡아야한다. 리프 노드를 하나씩 제거하면서 남은 값을 찾아나가면 해당 노드를 찾을 수 있다. 마지막에 남은 값이 짝수 개일 때는 루트가 2개가 될 수 있으므로 2까지 while을 돌린다.

public class Solution {
    public IList<int> FindMinHeightTrees(int n, int[][] edges) { 
        
        if (edges.Length == 0) return new List<int>() {0};
        List<List<int>> adjList = new List<List<int>>();
        
        for (int i = 0; i < n; i++)
        {
            adjList.Add(new List<int>());
        }
            
        for (int i = 0; i < edges.Length; i++) // 그래프 정보 초기화 
        {
            adjList[edges[i][0]].Add(edges[i][1]);
            adjList[edges[i][1]].Add(edges[i][0]);
        }
        
        Queue<int> queue = new Queue<int>();
        // 첫번째 리프노드 추가 
        for (int i=0; i < n; i++)
        {
            if(adjList[i].Count == 1) queue.Enqueue(i);
        }
        // 가장 연결이 많은 노드가 루트가 되어야 높이가 최소가 된다
        while (n > 2)
        {
            int size = queue.Count;
            // 루트 남길때까지 반복 제거 
            for (int i = 0; i < size; i++)
            {
                int currentLeaf = queue.Dequeue();
                int neighbor = adjList[currentLeaf][0];
                adjList[neighbor].Remove(currentLeaf);
                adjList[currentLeaf].Remove(neighbor);
                
                if (adjList[neighbor].Count == 1) // 다음 리프노드 할당 
                {
                    queue.Enqueue(neighbor);
                }
            }
            
            n = n - size;
        }
        
        return queue.ToArray();
    }
}

결과