[탐욕법] 섬 연결하기

yyeahh·2021년 2월 15일
0

프로그래머스

목록 보기
33/35

|| 문제설명 ||

  1. 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하라

  2. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 본다.

    예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능

cost : n개의 섬 사이에 다리를 건설하는 비용

_ 섬의 개수 n : 1 이상 100 이하
_ costs의 길이 : ((n-1) * n) / 2이하
_ 임의의 i에 대해, 
	costs[i][0] - costs[i] [1] : 연결되는 두 섬의 번호가 들어있고, 
	costs[i] [2] : 다리를 건설할 때 드는 비용
_ 같은 연결은 두 번 주어지지 않음(순서가 바뀌더라도 같은 연결)
_ 모든 섬 사이의 다리 건설 비용이 주어지지 않음(이 경우, 두 섬 사이의 건설이 불가능한 것)
_ 연결할 수 없는 섬은 주어지지 않음

|| 문제해결방법 ||

- Greedy알고리즘 중에서도 최장신장트리를 구하는 문제이다.
- 특히 같은 집단안에 있는지를 알아내는 Union-find를 활용하며 다음과 같은 방법으로 구현할 수 있다.
	1) 배열
    	2) 트리
- 이중에서 배열을 통해 집단의 루트만 표현하며


|| 코드 ||

[2021.02.17] 실패
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(vector<int> a, vector<int> b) {
    return a[2] == b[2] ? a[0] < b[0] : a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0, arr[n];
    
    for(int i = 0; i < n; i++) {
        arr[i] = i;
    }
    sort(costs.begin(), costs.end(), compare);
    for(int i = 0; i < costs.size(); i++) {
        if(costs[i][2] == 0) continue;
        
        if(arr[costs[i][0]] != arr[costs[i][1]]) {
            for(int j = 0; j < n; j++) {            //같은 루트를 가진 모든 다리의 루트를 변경
                if(arr[j] == arr[costs[i][1]])
                    arr[j] = arr[costs[i][0]];
            }
            answer += costs[i][2];
        }
    }
    return answer;
}

- 연결된 섬의 개수를 파악하여 그 뒤의 추가적인 일을 제한함.
#include <string>
#include <vector>
#include <algorithm>

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, cnt = 1, arr[n];
    
    for(int i = 0; i < n; i++) {
        arr[i] = i;
    }
    sort(costs.begin(), costs.end(), compare);
    for(int i = 0; i < costs.size(); i++) {
        if(costs[i][2] == 0 || arr[costs[i][0]] == arr[costs[i][1]]) continue;
        
        if(arr[costs[i][0]] != arr[costs[i][1]]) {
            for(int j = 0; j < n; j++) {            //같은 루트를 가진 모든 다리의 루트를 변경
                if(arr[j] == arr[costs[i][1]])
                    arr[j] = arr[costs[i][0]];
            }
            answer += costs[i][2];
            cnt++;
        }
        if(cnt == n) break;
    }
    return answer;
}

이전 코드는 모든 섬을 연결해도 추가적으로 if문 안으로 들어가는 경우가 발생한다는 점을 알 수 있다. → arr의 내용이 하나로 통일되지 않은 경우/루트를 변경할 때 오류가 생기는지

두번째 for문 안의 if(arr[j] == arr[costs[i][1]])에서 만약 기준이되는 값이 바뀌고 다음 값도 바뀌어야할 때 다르게 적용되므로 미리 arr[costs[i][1]의 값을 따로 저장하고 비교해준다.

그리고 모든 섬을 연결했을 때 실패한 경우가 생기는 것을 보아 기대값보다 크거나 작은 최소비용에 맞지 않는 경우가 일어남을 알 수 있다.

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

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, cnt = 1, arr[n];
    
    for(int i = 0; i < n; i++) {
        arr[i] = i;
    }
    sort(costs.begin(), costs.end(), compare);
    for(int i = 0; i < costs.size(); i++) {
        if(costs[i][2] == 0 || arr[costs[i][0]] == arr[costs[i][1]]) continue;
        
        int tmp = arr[costs[i][1]];
        for(int j = 0; j < n; j++) {            //같은 루트를 가진 모든 다리의 루트를 변경
            if(arr[j] == tmp)
                arr[j] = arr[costs[i][0]];
        }
        answer += costs[i][2];
        cnt++;

        if(cnt == n) break;
    }
    return answer;
}

0개의 댓글