코딩 테스트 대비: '네트워크 연결' 문제 풀이 - Kruskal 알고리즘 적용 (C#)

안녕하세요, GameLabMaster입니다! 이번 코딩 테스트 대비 포스팅에서는 '네트워크 연결' 문제와 해당 문제를 해결하는 Kruskal 알고리즘에 대해 알아보겠습니다.

 

문제

여러 개의 노드와 각 노드를 연결하는 간선들이 주어집니다. 각 간선은 가중치를 가지며, 이 가중치는 노드 간의 연결 비용을 의미합니다. 모든 노드를 연결하는 최소 비용을 구하는 프로그램을 작성하세요.

 

입력

• 노드의 개수 N (1 ≤ N ≤ 1000)
• 간선의 개수 M (1 ≤ M ≤ 100,000)
• M개의 간선 정보, 각 줄에는 노드 A, 노드 B, 가중치 C가 주어집니다. (1 ≤ A, B ≤ N, 1 ≤ C ≤ 100,000)

 

출력

• 모든 노드를 연결하는 최소 비용

 

풀이
이 문제는 Kruskal 알고리즘을 사용하여 해결할 수 있습니다. 우선 간선을 가중치의 오름차순으로 정렬한 후, 가장 작은 가중치부터 간선을 선택하여 노드를 연결합니다. 이때, 이미 같은 집합에 속한 노드를 연결하는 경우 사이클이 발생하므로, 해당 간선은 선택하지 않습니다. 모든 간선을 확인한 후 선택한 간선의 가중치를 더해 최소 비용을 구합니다.

다음은 C#으로 작성한 '네트워크 연결' 문제의 풀이 코드입니다.

 

using System;
using System.Collections.Generic;

class Edge {
    public int Node1;
    public int Node2;
    public int Cost;
}

class UnionFind {
    private int[] _parent;

    public UnionFind(int nodeCount) {
        _parent = new int[nodeCount + 1];

        for (int i = 1; i <= nodeCount; i++) {
            _parent[i] = i;
        }
    }

    public int Find(int node) {
        if (_parent[node] == node) {
            return node;
        }

        _parent[node] = Find(_parent[node]);
        return _parent[node];
    }

    public void Union(int node1, int node2) {
        int root1 = Find(node1);
        int root2 = Find(node2);

        if (root1 != root2) {
            _parent[root2] = root1;
        }
    }
}

class Program {
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        int m = int.Parse(Console.ReadLine());
        List<Edge> edges = new List<Edge>();

        for (int i = 0; i < m; i++) {
            string[] input = Console.ReadLine().Split(' ');
            int node1 = int.Parse(input[0]);
            int node2 = int.Parse(input[1]);
            int cost = int.Parse(input[2]);

            edges.Add(new Edge { Node1 = node1, Node2 = node2, Cost = cost });
        }

        edges.Sort((a, b) => a.Cost.CompareTo(b.Cost));

        UnionFind uf = new UnionFind(n);
        int totalCost = 0;

        foreach (Edge edge in edges) {
            if (uf.Find(edge.Node1) != uf.Find(edge.Node2)) {
                uf.Union(edge.Node1, edge.Node2);
                totalCost += edge.Cost;
            }
        }

        Console.WriteLine(totalCost);
    }
}

 

이 코드는 먼저 간선 정보를 입력받아 edges 리스트에 저장한 후, 간선들을 가중치의 오름차순으로 정렬합니다. 그 다음 Union-Find를 사용하여 노드를 연결하면서 최소 비용을 구하고 출력합니다.

 

이렇게 Kruskal 알고리즘을 이용하여 '네트워크 연결' 문제를 해결할 수 있습니다. 이 알고리즘을 익히면 다양한 최소 신장 트리 문제를 쉽게 해결할 수 있으므로, 코딩 테스트 대비에 도움이 될 것입니다. 다음 포스팅에서는 다른 그래프 알고리즘에 대해 알아보겠습니다.