[Level 3] 섬 연결하기

 

각 노드를 최소 비용으로 연결시키는 문제이다. 최소 신장 트리를 만드는 Kruskal 알고리즘을 사용하면 된다. 알고리즘은 간단하다. 우선 cost를 기준으로 오름차순 정렬시킨다.

i번 째 cost를 골라 두 섬이 연결되어 있는지 확인한다. 만약 연결되어 있다면(같은 그룹이라면) 다시 연결할 필요없다. 만약 연결되어 있지 않다면 (같은 그룹이 아니라면) 두 노드를 연결시키고(같은 그룹으로 표시) 해당 비용을 누적시킨다.

이를 모든 costs 요소에 대해 확인하면 된다. 

여기서 핵심은 두 섬이 서로 연결되어 있는지, 같은 그룹에 있는지 확인하는 방법이다. 방법은 생각보다 간단한다. 우선 섬의 개수인 n의 크기를 가지는 int 타입 원소를 저장하는 1차원 배열을 하나 생성한다. 초기값은 모두 -1로 설정한다.

배열의 이름은 groupIDs이다. groupIDs[i]는 섬 i가 속한 그룹의 값이다. groupIDs[0] == groupIDs[2]이면 섬 0과 2는 서로 같은 그룹에 속해있는 것이다. 즉 연결되어 있다고 본다. 값 설정의 기준은 상관없다.

만약 현재 cost가 2이고 두 노드(섬)가 0, 2라면 두 노드의 그룹ID를 확인한다. 만약 두 값이 모두 -1이라면, 어디에도 연결되어 있지 않으므로 두 노드를 하나의 그룹으로 만든다. 여기서 그룹ID는 두 노드의 ID(0, 2)중 더 작은 값으로 설정한다. 즉 groupIDs[0] == groupIDs[2] == 0이 된다.

또 다른 경우로 하나의 노드는 그룹에 속해있고 하나의 노드는 그룹이 없을 수 있다. 그럼 그룹이 없는 노드를 다른 노드의 그룹으로 포함시킨다. 만약 노드 2와 3에 대해 groupIDs[2] == 0이고 groupIDs[3] == -1일 경우 groupIDs[3] = 0으로 만들어주면 된다.

또 다른 경우로 두 노드 모두 그룹이 있는 경우이다. 여기는 두 가지로 나뉜다. 같은 그룹에 속해 있거나 다른 그룹에 속해있거나.

같은 그룹에 속해 있다면 굳이 연결할 필요가 없으므로 스킵한다. 같은 그룹이 아니라면 두 그룹을 합쳐야 한다.(연결시켜야 한다.) 만약 groupIDs[3] == 0이고 groupIDs[6] == 6이라면, 노드 6을 노드 3 그룹에 포함시키던가, 그 반대로 해야한다. 아무거나 상관은 없지만 여기선 더 작은 그룹ID로 이동시킨다. 단순히 노드 6의 그룹ID만 변경하면 안되고, groupIDs를 돌면서 값이 6인 노드를 모두 0으로 변경해주어야 한다. 

이를 반복할 때마다 cost를 누적시켜주면 정답이 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> costs) {

    // cost 기준 오름차순 정렬
    sort(costs.begin(), costs.end(), [](const vector<int>& v1, const vector<int>& v2)
         {
            return v1[2] < v2[2]; 
         });
    
    // groupIDs[i] => 섬 i가 속해있는 그룹ID
    vector<int> groupIDs(n, -1);
    int minCost = 0;
    
    for(int i = 0; i < costs.size(); ++i)
    {
        int id1 = costs[i][0];
        int id2 = costs[i][1];
        int cost = costs[i][2];
        
        // 두 노드가 아직 어떤 그룹에도 속해있지 않다면
        if(groupIDs[id1] == -1 && groupIDs[id2] == -1)
        {
            // 두 노드의 그룹 ID를 둘 중 더 작은 id로 설정
            int newGroupID = min(id1, id2);
            groupIDs[id1] = newGroupID;
            groupIDs[id2] = newGroupID;
        }
        else if(groupIDs[id1] == -1 || groupIDs[id2] == -1)
        { // 두 노드 중 하나만 그룹에 속해 있는 경우
            // 그룹에 속해 있지 않은 섬의 그룹ID를 
            // 다른 노드가 속해 있는 그룹ID로 설정
            if(groupIDs[id1] == -1)
                groupIDs[id1] = groupIDs[id2]; 
            else
                groupIDs[id2] = groupIDs[id1]; 
        }
        else // 두 노드 모두 (서로 다른) 그룹에 속해 있는 경우
        {
            // 두 노드가 같은 그룹이면 연결하지 않음
            if(groupIDs[id1] == groupIDs[id2])
                continue;
            
            // groupIDs(id1) 과 groupIDs(id2) 중 더 작은 값으로 통일
            // ex) groupIDs(id1): 3, groupIDs(id2): 5라면
            // groupIDs(x) = 5인 모든 값을 3으로 변경
            int maxGroupID = max(groupIDs[id1], groupIDs[id2]);
            int minGroupID = min(groupIDs[id1], groupIDs[id2]);
            
            for(int i = 0; i < groupIDs.size(); ++i)
            {
                if(groupIDs[i] == maxGroupID)
                    groupIDs[i] = minGroupID;
            }
        }
        
        // cost 추가
        minCost += cost;
    }
    
	return minCost;
}