[프로그래머스 42861]섬 연결하기

문제링크

programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

문제난이도

Level3

 

문제풀이

※최소비용을 구하기 위해서 Union-Find 알고리즘을 이용해서 풀이해보았다※

1. 각 노드들의 부모를 초기 설정 해준다

   - 처음에는 연결된 노드가 없으므로 자기자신이 부모가 된다

2. 주어진 노드간의 비용을 기준으로 오름차순 정렬을 한다

3. 주어진 노드 정보 탐색을 시작한다

   3-1. 연결될 두 노드의 부모가 같은 경우, 순환이 발생되어 최소비용의 조건이 깨지므로 연산하지 않는다

   3-2. 연결될 두 노드의 부모가 다른 경우, 노드끼리 연결하고 부모를 합쳐준다

   ☞ 각 노드의 부모를 찾고, 부모를 합쳐주기 위해 이때 Union-Find 알고리즘을 적용하여 풀이한다

4. 연결된 두 노드의 이동비용을 합산해준다

 

 

소스코드

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> parent(101);
 
bool cmp(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}
 
int getParent(int x) {
    //노드x의 부모가 본인(x)인 경우, x 반환
    if (parent[x] == x) {
        return x;
    }
 
    //부모가 다른 노드인 경우, 가리키는 부모값으로 다시 부모노드를 찾는다(재귀)
    return parent[x] = getParent(parent[x]);
}
 
void unionParent(int a, int b) {
    //각 노드의 부모노드를 찾는다
    int parentA = getParent(a);
    int parentB = getParent(b);
 
    //부모노드 값이 더 작은쪽이 상대 노드의 부모가 된다
    if (parentA < parentB) {
        parent[parentB] = parentA;
    }
    else {
        parent[parentA] = parentB;
    }
}
 
bool findParent(int a, int b) {
    //해당 노드의 부모를 찾아준다
    int parentA = getParent(a);
    int parentB = getParent(b);
 
    //부모가 같으면 true, 다르면 false르 반환한다
    if (parentA == parentB) {
        return true;
    }
    return false;
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
 
    //아직 연결된 노드가 없으므로 본인을 본인의 부모로 설정한다
    for (int i = 0; i < costs.size(); i++) {
        parent[costs[i][0]] = costs[i][0];
        parent[costs[i][1]] = costs[i][1];
    }
 
    //섬간의 거리를 기준으로 오름차순 정렬한다
    sort(costs.begin(), costs.end(), cmp);
 
    for (int i = 0; i < costs.size(); i++) {
        //부모가 같은경우(순환 발생) continue
        if (findParent(costs[i][0], costs[i][1]) == true) {
            continue;
        }
        
        //부모가 다른경우, 노드끼리 연결을 통해 부모를 합쳐준다
        unionParent(costs[i][0], costs[i][1]);
 
        //섬간의 이동 비용을 합산해준다
        answer += costs[i][2];
    }
 
    return answer;
}