[C#] 섬연결하기 - 크루스칼 알고리즘 , 그리디 알고리즘

프로그래머스 문제

 

문제 설명

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

풀이

using System;
using System.Collections.Generic;

public class Solution
    {
        public int solution(int n, int[,] costs)
        {
            int[,] distance = new int[n, n] ;
            int i, j;

            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    distance[i, j] = -1;
                }
            }
            for(i=0;i<costs.GetLength(0);i++)
            {
                distance[costs[i,0], costs[i,1]] = costs[i, 2];
                distance[costs[i,1], costs[i,0]] = costs[i, 2];
            }
            HashSet<int> ans = new HashSet<int>();
            ans.Add(0);
            int min;
            int minIdx = -1;
            int answer = 0;
            while (ans.Count < n)
            {
                min = 9999999;
                foreach(int it in ans)
                {
                    for(i=0;i<n;i++)
                    {
                        if (ans.Contains(i))
                            continue;
                        if(distance[it,i] != -1 && distance[it,i] < min)
                        {
                            min = distance[it, i];
                            minIdx = i;
                        }
                    }
                }
                answer += min;
                ans.Add(minIdx);
            }
            return answer;
        }
    }

느낀점: 우선 문제의 규칙은 파악하였으나 부족한 실력탓에 다른분의 코드를 조금 참조하였다.

 

프로그래머스 고득점 킷에 그리디 알고리즘으로 등록되어있으며 핵심 알고리즘으로는 크루스칼 알고리즘이 사용된다

 

크루스칼 알고리즘이란 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.

 

그리디 알고리즘은 앞서 말한 것처럼 순차적으로 바뀌는 우선순위를 파악하는 것이 중요한데 이 문제에서는

 

1. 가장 비용이 낮은 연결고리의 섬들부터 연결해준다.

 

2.이미 연결된 섬들끼리의 연결은 Skip해준다.

 

3.모든 섬이 연결되었을때의 값을 리턴하여 남은 연결고리는 Skip하여준다.

 

위 세가지 조건을 충족시켰을 때 값이 도출된다.