[프로그래머스] Level 3. 섬 연결하기

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

프로그래머스

 

 

해결 방법

• 비용이 적은 다리 순으로 나열한다.
• 연결할 필요가 있다면 연결한다. 연결할 필요는 어떻게 판단하나?
  • 서로 연결된 지점들은 트리로 연결되어 있다. 두 지점이 연결되어있는지 확인하기 위해서는 자신의 루트노드를 찾고, 두 지점의 루트노드가 같다면 이미 다리를 이용해 연결되어있다는  의미이다. 
  • 만약 두 지점의 루트노드가 같다면 연결하지 않고 넘어간다.
  • 루트노드가 다르다면, 두 트리를 연결한다. 하나의 루트노드를 다른하나의 루트노드에 연결한다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int findRoot(vector<int>& parents, int i){
    while(true){
        if(parents[i] == -1) return i;
        i = parents[i];
    }
}

int solution(int n, vector<vector<int>> costs) {
    sort(costs.begin(), costs.end(), [](vector<int>& a, vector<int>& b){return a[2]< b[2];});
    vector<int> parent(n,-1);
    int answer = 0;
    
    for(int i=0; i<costs.size(); i++){
        int a = findRoot(parent, costs[i][0]);
        int b = findRoot(parent, costs[i][1]);
        if(a == b) continue;
        
        answer += costs[i][2];
        parent[a] = b;
    }
    
    return answer;
}

 

 

마무리하며

매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 것을 "그리디 알고리즘(탐욕법)" 이라고 한다. 그리디 알고리즘은 항상 최적의 값을 보장하는 것이 아니라 최적의 값에 근사한 값을 목표로 한다.

이 문제는 그리디 알고리즘에, 트리를 이용하여 불필요한 다리를 검사하는 방법을 사용했다.

여러가지 알고리즘을 알고있고, 문제에  맞는 적절한 알고리즘을 고르는게 중요한 것 같다.