C# 프로그래머스 LV3 섬 연결하기

2024. 3. 12. 13:30C# 프로그래머스

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

  • 섬의 개수 n은 1 이상 100 이하입니다.
  • costs의 길이는 ((n-1) * n) / 2이하입니다.
  • 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
  • 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
  • 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
  • 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n costs return
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

 

이 문제는 서로 이어진 최단 경로들을 구하는 대표 문제이다.

나는 Kruskal 알고리즘을 공부해서 Kruskal 알고리즘을 이용해서 풀었다.

 

 

using System;
using System.Collections.Generic;

public class Solution 
{
    public int solution(int n, int[,] costs)
    {
                      
        int[] vertex = new int[n];       
        int answer = 0;                  
        
        for(int i = 0; i < vertex.Length; i++)        
        {         
            vertex[i] = i;      
        }          
        
        Graph graph = new Graph(vertex);       
        
        for(int i = 0; i < costs.GetLength(0); i++)
        {
            graph.AddEdge(costs[i , 0], costs[i , 1], costs[i , 2]);
        }
        
        answer = graph.KruskalMST();
        return answer;
    }    
}
 
public class DisJoint 
{
        Dictionary<int, int> ht = new Dictionary<int, int>();
        public DisJoint()
        {
            ht = new Dictionary<int, int>();
        }
        public void GetNode(int node)
        {
            ht[node] = node;
        }
        public void UnionParent(int ele1, int ele2) 
        {
            ht[ele1] = ele2;
        }
        public int FindParent(int node)
        {
            if (ht[node] == node)
            {
                return node;
            }
            else
            {
                return FindParent(ht[node]);
            }
        }
  
}

 public class Edge
    {
        public int From { get; }
        public int To { get; }
        public int Weight { get; }

        public Edge(int from, int to, int weight)
        {
            From = from;
            To = to;
            Weight = weight;
        }
    }
 public class Graph
 {  
     private readonly List<int> vertexs;  
     private List<Edge> edges;   
     private bool digraphed;   
     private int answer; 
     public Graph(IEnumerable<int> vertex, bool digraphed = false)       
     {              
         vertexs = new List<int>(vertex);              
         edges = new List<Edge>();          
         this.digraphed = digraphed;      
     }

        public void AddEdge(int from, int to, int weight)
        {
            edges.Add(new Edge(from, to, weight));

            if (!digraphed)
            {
                edges.Add(new Edge(to, from, weight));
            }
        }

        public int KruskalMST()
        {
            DisJoint disj = new DisJoint();

            for(int i = 0; i < vertexs.Count; i++)
            {
                disj.GetNode(vertexs[i]);
            }         
            edges.Sort((ele1, ele2) => ele1.Weight - ele2.Weight);

            foreach (Edge edge in edges)
            {
                int ele1 = disj.FindParent(edge.From);
                int ele2 = disj.FindParent(edge.To);

                if (ele1 != ele2)
                {
                    disj.UnionParent(ele1, ele2);
                    answer += edge.Weight;
                }
            }

            return answer;
        } 
 }

'C# 프로그래머스' 카테고리의 다른 글

C# 백준 1753 최단경로  (0) 2024.03.12
C# 프로그래머스 LV2 무인도여행  (0) 2023.11.07