[프로그래머스 C#] Lv.3 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

최소 신장 트리(MST) 알고리즘 문제

- 섬 : 정점 / 다리 : 간선 / 비용 : 가중치 로 두고 풀이

- 대표적 MST 문제로, 크루스칼 알고리즘, 프림 알고리즘으로 각각 풀어봄

 

+ 해당 문제의 주어진 그래프의 간선의 개수는 최대 ((n-1) * n / 2) 개로 간선이 많은 밀집 그래프보다는 간선이 적은 희소 그래프에 더 가깝기 때문에, 간선을 기준으로 선택하는 크루스칼 알고리즘이 더 유리함

 

최소 신장 트리 MST ( 크루스칼, 프림 )

https://godgjwnsgur7.tistory.com/112

[Algorithm C#] 최소 신장 트리 MST ( 크루스칼, 프림 )

1) 크루스칼 알고리즘 풀이 정답코드

가장 비용이 적은 간선부터 선택해 나감

- 주어진 간선정보를 커스텀 데이터클래스 리스트로 담아 가중치를 기준으로 오름차순 정렬

- 서로 연결되어있는 정점의 그룹은 연결된 정점 중에 가장 번호가 낮은 정점의 번호를 가짐

 -> 루트(부모) 정점의 번호를 가짐

 

풀이 순서

- 주어진 간선정보를 커스텀 데이터클래스 리스트로 담아 가중치를 기준으로 오름차순 정렬

- 가장 가중치가 낮은 간선부터 모든 간선을 탐색하며, 두 정점이 이어져있지 않다면 병합

 -> 두 정점의 루트(부모) 정점의 번호가 다르다면 이어져있지 않음

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        // 두 정점과 가중치를 담은 간선에 대한 데이터클래스
        public class DataClass
        {
            public int x; // 정점1
            public int y; // 정점2
            public int cost; // 가중치
            
            public DataClass(int x, int y, int cost)
            {
                this.x = x;
                this.y = y;
                this.cost = cost;
            }
        }

        // 부모(루트)를 반환
        public int GetRoot(int[] parents, int x)
        {
            if (parents[x] == x)
                return x;
             
            return parents[x] = GetRoot(parents, parents[x]);
        }

        // 같은 부모(루트)로 병합
        public void Union(int[] parents, int x, int y)
        {
            x = GetRoot(parents, x);
            y = GetRoot(parents, y);

            if (x > y) parents[y] = x;
            else parents[x] = y;
        }

        // 같은 부모(루트)를 가졌는지 판단
        public bool Find(int[] parents, int x, int y)
        {
            x = GetRoot(parents, x);
            y = GetRoot(parents, y);

            return x == y;
        }

        public int solution(int n, int[,] costs)
        {
            int answer = 0;

            var parents = new int[n]; // 부모의 인덱스를 가리키는 배열     
            var list = new List<DataClass>();

            // 초기 세팅
            for (int i = 0; i < parents.Length; i++)
                parents[i] = i;

            for (int i = 0; i < costs.GetLength(0); i++)
                list.Add(new DataClass(costs[i, 0], costs[i, 1], costs[i, 2]));

            // 비용을 기준으로 오름차순 정렬
            list.Sort((x, y) => x.cost < y.cost ? -1 : 1);

            // 비용이 가장 낮은 간선부터 판단
            for (int i = 0; i < list.Count; i++)
            {
                if (Find(parents, list[i].x, list[i].y))
                    continue;

                // 같은 부모를 가지지 않았다면, 병합
                Union(parents, list[i].x, list[i].y);
                answer += list[i].cost; // 해당 간선을 연결
            }

            return answer;
        }
    }

2) 프림 알고리즘 풀이 정답코드

임의의 시작 정점부터 인접한 정점을 선택해 나감

- 가중치 2차원 배열 costArray[x, y]의 값은 섬의 번호를 인덱스로 하여 x -> y 의 가중치를 가짐

- 연산 최적화를 위해 연결된 정점 배열과 연결되지 않은 정점들을 가지는 배열 선언

 

풀이 순서

- 임의의 정점에서 시작 ( 풀이에서는 무조건 존재하는 0번 정점으로 세팅 )

- 모든 정점을 이을 때까지 인접한 정점 중에 가장 가중치가 낮은 간선을 연결하는 것을 반복

+ 인접한 정점 : 현재 연결된 정점 그룹과 간선으로 연결된 정점

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int solution(int n, int[,] costs)
        {
            int answer = 0;
            int[,] costArray = new int[n, n]; // 통행 비용(가중치) 배열 - 가중치가 0이라면 간선없음
            List<int> visitList = new List<int>(); // 연결된 섬의 인덱스 번호 (연결된 정점)
            List<int> visitedList = new List<int>(); // 연결되지 않은 섬의 인덱스 번호 (연결되지 않은 정점)

            // 가중치 배열 세팅
            for (int i = 0; i < costs.GetLength(0); i++)
            {
                costArray[costs[i, 1], costs[i, 0]] = costs[i, 2];
                costArray[costs[i, 0], costs[i, 1]] = costs[i, 2];
            }

            // 방문 배열, 미방문 배열 초기 값 세팅
            visitList.Add(0);
            for (int i = 1; i < n; i++)
                visitedList.Add(i);

            // 모든 정점이 연결될 때까지 반복
            while (visitList.Count != n)
            {
                int minValue = 99999; // 최소 가중치 값
                int index = 0; // 최소 가중치로 연결된 정점

                for (int i = 0; i < visitList.Count; i++)
                {
                    for (int j = 0; j < visitedList.Count; j++)
                    {
                        // 연결 가능한 정점과의 간선 중에 가중치가 최소인 간선 찾기
                        if (0 < costArray[visitList[i], visitedList[j]]
                          && costArray[visitList[i], visitedList[j]] < minValue)
                        {
                            minValue = costArray[visitList[i], visitedList[j]];
                            index = visitedList[j];
                        }
                    }
                }

                // 선택된 간선을 연결해 연결된 정점을 포함, 가중치 값 추가
                visitList.Add(index);
                visitedList.Remove(index);
                answer += minValue;
            }

            return answer;
        }
    }