<Lv.3> 섬 연결하기 (프로그래머스 : C#)

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

📕 문제 설명

n개의 섬 사이 다리 건설 비용이 주어질 때, 모든 섬을 통행할 수 있게 하는 최소 비용 반환

• Input
  n, 섬 사이 다리 건설 비용 정보
• Output
  모든 섬 통행할 수 있게 하는 최소 비용

예제

풀이

다익스트라로 최소 비용 가지는 다리들 뽑으면서 방문 안한 경우 해당 다리를 건설하는 방식으로 구현했다.

(이거 프로그래머스 dotnet 버전이 낮은건지 PriorityQueue (6버전 부터 지원일텐데..) 같은 클래스가 아예 import해서 쓸 수가 없다는 치명적 단점이 있다.. ㅎ 그래서 그냥 minHeap 클래스로 구현해서 사용했다.)

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] costs) {
        bool[] visited = new bool[n];
        List<(int island, int cost)>[] adjList = new List<(int island, int cost)>[n];
        
        // 그래프 초기화
        for (int i = 0; i < n; i++)
        {
            adjList[i] = new List<(int island, int cost)>();
        }
        
        for (int i = 0; i < costs.GetLength(0); i++)
        {
            int firstIsland = costs[i, 0];
            int secondIsland = costs[i, 1];
            int cost = costs[i, 2];
            
            adjList[firstIsland].Add((secondIsland, cost));
            adjList[secondIsland].Add((firstIsland, cost));
        }
        
        int minCost = 0;
        // 최소 비용인 간선 뽑아서 확인해나가는 식 
        PriorityQueue pq = new PriorityQueue();
        pq.Enqueue(0, 0);
        
        while (pq.Count() > 0)
        {
            var currInfo = pq.Dequeue();
            int currIsland = currInfo.Item1;
            int cost = currInfo.Item2;
            
            if (visited[currIsland]) continue;
            
            visited[currIsland] = true;
            minCost += cost;
            
            foreach (var adjInfo in adjList[currIsland])
            {
                if (!visited[adjInfo.island])
                {
                    pq.Enqueue(adjInfo.island, adjInfo.cost);
                }
            } 
        }
        
        return minCost;
    }
}

public class PriorityQueue
{
    List<(int island, int cost)> _heap = new List<(int island, int cost)>();
    
    public void Enqueue(int island, int cost)
    {
        _heap.Add((island, cost));
        
        int now = _heap.Count - 1;
        while(now > 0)
        {
            int next = (now-1)/2; // 부모 
            if(_heap[now].cost > _heap[next].cost) break;
            // 들어온 데이터 <= 부모 -> swap
            var temp = _heap[now];
            _heap[now] = _heap[next];
            _heap[next] = temp;
            
            now = next; // 검사 위치 이동
        }
    }
    public (int, int) Dequeue()
    {
        var ret = _heap[0];
        
        // 마지막 데이터 루트로 이동
        int lastIndex = _heap.Count - 1;
        _heap[0] = _heap[lastIndex];
        _heap.RemoveAt(lastIndex);
        lastIndex--;
        
        int now = 0; // 현재
        while(true)
        {
            int left = 2 * now + 1;
            int right= 2 * now + 2;
            
            int next = now; 
            if(left <= lastIndex && _heap[next].cost >= _heap[left].cost) next = left;
            if(right <= lastIndex && _heap[next].cost >= _heap[right].cost) next = right;
            if(next == now) break;
            
            var temp = _heap[now];
            _heap[now] = _heap[next];
            _heap[next] = temp;
            
            now = next;
        }
        return ret;
    }
    
    public int Count()
    {
        return _heap.Count;
    }
}

결과