[프로그래머스 LV3] 섬 연결하기 (그리디, 유니온파인드) [C++]

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

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

주어진 노드와 cost 정보로 최소의 비용으로 섬들 간 연결을 하면 된다.

1 - 2 - 3이 연결되려면 모든 노드가 연결되어 있을 필요가 없이 1 - 2, 2 - 3만 되어있어도 1, 2, 3이 모두 연결되었다고 한다.

 

처음에 어떻게 풀지 고민을 하다가, 그래프 관련 알고리즘으로 풀어보려고 했다.

BFS를 사용하면 방문하는 순서에 따라서 최솟값을 못 찾을 수도 있다는 결론이 나와서 pass

(모든 점에서 BFS를 통해 최단 경로를 찾은 뒤, 최저 값을 출력하려고 했지만 cost가 높은 path를 먼저 visit 해버리면 찾지 못하겠다는 생각이 들었다.)

 

그렇다면 cost가 작은 것부터 방문해서 우선순위 큐를 사용할까? 생각이 들었다가 

아 그냥 정렬해버리고 방문한 점들을 집합에 넣어버리자 라는 생각이 들었다.

 

그래서 결론적으로 costs 정렬을 cost을 기준으로 오름차순으로 정렬하고, union-find를 통해 하나하나 체크해주었다.

 

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

using namespace std;

int parent[101];

bool compare(vector<int> &v1, vector<int> &v2){
    return v1[2] < v2[2];
}

int getParent(int a){
    if(a == parent[a]){
        return parent[a];
    }
    else
        return parent[a] = getParent(parent[a]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    
    if(a > b){
        parent[a] = b;
    }
    else{
        parent[b] = a;
    }
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(), costs.end(), compare);
    
    for(int i = 0 ; i < n ; i++){
        parent[i] = i;
    }
    
    for(int i = 0 ; i < costs.size() ; i++){
        int from = costs[i][0];
        int to = costs[i][1];
        int cost = costs[i][2];
        
        if(getParent(from) != getParent(to)){
            unionParent(from, to);
            answer += cost;
        }
    }
    
    return answer;
}

정렬한 노드들을 하나하나 방문하면서 노드의 parent를 통해 판단해준다.

만약 두 노드의 parent가 같으면 이미 그 두 점은 방문한 것이고, parent가 다르면 union 해서 같이 묶어주면서 cost를 더해주었다.

 

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

정렬 후 -> 

[[0,1,1],[1,3,1],[0,2,2],[1,2,5],[2,3,8]]

이고 테이블 초기화를 각 숫자로 해주었으므로

0-1 -> 부모가 다르므로 방문 안 함 -> cost 1을 더해주고 두 노드 부모가 0 0으로 변환

1-3 -> 역시 방문하지 않음 -> cost 1 더해주고 두 노드 부모 역시 0 0으로 변환 (노드 1의 부모가 0이었기에)

0-2 -> 역시 방문 X -> cost 2 더해주고 두 노드도 0 0으로 변환

1-2 -> 부모가 둘 다 0이므로 이미 어떤 경로를 통해서 연결되어있다 -> pass

2-3 -> 역시 부모가 동일 = 연결되어 있음

 

결과 cost 4가 출력된다.

 

다른 사람의 풀이를 보았더니 나와 똑같이 정렬-unionFind로 풀었다.

그리디를 생각 안 했지만 이 방식이 그리디 하게 푼 풀이 같다.