프로그래머스 문제 - 섬 연결하기

프로그래머스 섬 연결하기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

n개의 섬의 갯수와 양방향으로 섬들을 잇는 간선들과 다리 비용이 주어집니다.
최소의 비용을 사용하여 모든 섬이 통행 가능하도록 해야 합니다.

노드 사이의 거리를 생각해야 합니다.

문제 풀이

모든 정점이 최소 비용으로 연결되어야 되기 때문에 크루스칼 알고리즘을 사용하였습니다.
최소 비용을 필요로 하기 때문에 비용을 기준으로 sort를 사용하였습니다

bool compare(vector<int> a, vector<int> b) {return a[2] < b[2];}

sort(costs.begin(), costs.end(), compare);

Union-Find를 사용하여 연결된 섬들을 기록하였습니다.
모든 섬이 연결되기 위해서는 n-1만큼 간선이 연결되어야 하기 때문에 n-1만큼만 연결한 후 멈춰줍니다.

if(check[costs[i][0]] != check[costs[i][1]])
{
	int bigTemp, smallTemp;
    answer += costs[i][2];
    if(check[costs[i][0]] < check[costs[i][1]])
    {
        bigTemp = check[costs[i][1]];
        smallTemp = check[costs[i][0]];
    }
    else
    {
        bigTemp = check[costs[i][0]];
        smallTemp = check[costs[i][1]];
        check[costs[i][0]] = check[costs[i][1]];
    }
    for(int j = 0; j < n; j++)
    {
        if(check[j] == bigTemp)
        {
            check[j] = smallTemp;
        }
    }
    cnt++;
}

전체 코드

이번 문제는 그리디의 알고리즘 중 크루스칼 알고리즘을 배우는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

bool compare(vector<int> a, vector<int> b) {return a[2] < b[2];}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int check[100];
    int cnt = 0;
    
    for(int i = 0; i < n; i++)
    {
        check[i] = i;
    }
    
    sort(costs.begin(), costs.end(), compare);
    
    for(int i = 0; i < costs.size(); i++)
    {           
        if(check[costs[i][0]] != check[costs[i][1]])
        {
            int bigTemp, smallTemp;
            answer += costs[i][2];
            if(check[costs[i][0]] < check[costs[i][1]])
            {
                bigTemp = check[costs[i][1]];
                smallTemp = check[costs[i][0]];
            }
            else
            {
                bigTemp = check[costs[i][0]];
                smallTemp = check[costs[i][1]];
                check[costs[i][0]] = check[costs[i][1]];
            }
            for(int j = 0; j < n; j++)
            {
                if(check[j] == bigTemp)
                {
                    check[j] = smallTemp;
                }
            }
            cnt++;
        }
        if(cnt == n - 1)
        {
            break;
        }
    }
    
    return answer;
}

출저

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