[BOJ][C#] 1197 최소 스패닝 트리

📕 문제

📌 링크

📗 접근 방식

1. 간선들을 가중치 기준으로 오름차순으로 정렬
2. 가장 가중치가 작은 간선부터 선택하여 그래프에 추가
3. 추가하려는 간선의 양 끝점이 같은 집합에 속해있는지 확인
   • 속해있다면, 해당 간선을 추가하면 싸이클이 생기므로 무시
   • 속해있지 않다면, 해당 간선을 추가하고 두 노드의 집합을 합체
4. 모든 간선에 대해 이를 반복하며 최소 비용 신장 트리를 구함
5. 최소 비용 신장 트리의 간선들의 가중치 합을 구하여 반환

📘 코드

namespace BOJ
{
    static class Input<T>
    {
        public static T[] GetArray() => Array.ConvertAll(Console.ReadLine().Split(), ConvertTo);
        private static T ConvertTo(string input) => (T)Convert.ChangeType(input, typeof(T));
    }
    
    class Edge 
    {
        public int u;
        public int v;
        public int weight;

        public Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }
    
    class No_1197
    {
        static int[] Parent = new int[10001];
        
        static void Main()
        {
            List<Edge> edges = new List<Edge>();
            long ans = 0;
            var input = Input<int>.GetArray();
            int V = input[0];
            int E = input[1];

            for (int i = 0; i < V; i++)
            {
                Parent[i] = i;
            }

            for (int i = 0; i < E; i++)
            {
                input = Input<int>.GetArray();
                int u = input[0];
                int v = input[1];
                int weight = input[2];
                edges.Add(new Edge(u, v, weight));
            }

            edges.Sort(MyCompare);

            foreach (var edge in edges.Where(edge => !IsSameParent(edge.u, edge.v)))
            {
                Union(edge.u, edge.v);
                ans += edge.weight;
            }

            Console.WriteLine(ans);
        }
        
        static int Find(int x) {
            if (Parent[x] == x)
                return x;
            
            return Parent[x] = Find(Parent[x]);
        }

        static void Union(int x, int y) {
            x = Find(x);
            y = Find(y);
            
            if (x != y) Parent[y] = x;
        }

        static bool IsSameParent(int x, int y) {
            x = Find(x);
            y = Find(y);
            
            return x == y;
        }

        static int MyCompare(Edge a, Edge b) {
            return a.weight.CompareTo(b.weight);
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리