lv3 ) 섬 연결하기 [다시]

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

프로그래머스

 

4번째 코드 정답

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


//크루스칼알고리즘
//1. 비용 기준 높은 순 정렬, 2. 유니온파인드, 3. n-1개 간선 까지의 비용 합
int org[101]; // 섬 100이하  , bool 타입으로 하면 segmentation 에러 발생 유의
bool comp(vector<int> base, vector<int> tar) {
	return base[2] < tar[2]; // std::sort 비교함수는 strict weak ordering 규칙을 따라야 해서 같을 때 반드시 false를 반환해야한다. 즉 <= 으로 true 시 런타임에러 발생 가능
}

int getParent(int now)
{
	if (org[now] == now) return now; // 0번째 섬부터 시작하는데 0이 보스가 아닐 수 있으나 항상 여기서 리턴됨.

	int ret = getParent(org[now]);
	org[now] = ret; // 최상위 부모노드의 자식들을 일렬로 배치
	return ret;
}
bool unionFind(int src1, int src2) {
	int parent1 = getParent(src1);
	int parent2 = getParent(src2);
	if (parent1 == parent2) return false;
	org[parent1] = parent2;
	return true;
}
int solution(int n, vector<vector<int>> costs) {
	int answer = 0; // 간선 비용 합
	int cnt = 0; // n-1개 카운팅 용도

	//초기 부모를 자기자신으로 초기화
	for (int idx = 0; idx < sizeof(org) / sizeof(org[0]); ++idx) org[idx] = idx;
	sort(costs.begin(), costs.end(), comp);

	for (int idx = 0; idx < costs.size(); ++idx) { 
		bool isConn = unionFind(costs[idx][0], costs[idx][1]);
		if (isConn) {
			cnt++;
			answer += costs[idx][2];
			if (cnt == n - 1)break;
		}
	}
	return answer;
}

 

유니온파인드에서는 어떤 순서로 인자 값을 넣든 결과는 같다. org[parent1] = parent2 로 합치기 때문에 인자 순서가 바뀌어도 동일 그룹이 된다. 

 

 

세번째 코드 오답

if (org[now] == 0) return now; // 0번째 섬부터 시작하는데 0이 보스가 아닐 수 있으나 항상 여기서 리턴됨.

 

 

두번째 코드 (크루스칼 알고리즘을 이용한 MST 기법 활용)

-그래프에서 최소 비용으로 모든 구간을 거쳐가는 문제이기에 MST(Minimum Spanning Tree)를 사용해야한다.

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


//크루스칼알고리즘
//1. 비용 기준 높은 순 정렬, 2. 유니온파인드, 3. n-1개 간선 까지의 비용 합
int org[101]; // 섬 100이하  , bool 타입으로 하면 segmentation 에러 발생 유의
bool comp(vector<int> base, vector<int> tar) {
	return base[2] < tar[2]; // std::sort 비교함수는 strict weak ordering 규칙을 따라야 해서 같을 때 반드시 false를 반환해야한다. 즉 <= 으로 true 시 런타임에러 발생 가능
}

int getParent(int now)
{
	if (org[now] == 0) return now; // 0번째 섬부터 시작하는데 0이 보스가 아닐 수 있으나 항상 여기서 리턴됨.
	
    int ret = getParent(org[now]);
	org[now] = ret; // 최상위 부모노드의 자식들을 일렬로 배치
	return ret;
}
bool unionFind(int src1, int src2) {
	int parent1 = getParent(src1);
	int parent2 = getParent(src2);
	if (parent1 == parent2) return false;
	org[parent1] = parent2;
	return true;
}
int solution(int n, vector<vector<int>> costs) {
	int answer = 0; // 간선 비용 합
	int cnt = 0; // n-1개 카운팅 용도
	sort(costs.begin(), costs.end(), comp);
	for (int idx = 0; idx < costs.size(); ++idx) { // costs.size()까지가 아닌 n-1 간선(n 정점 갯수 - 1)까지
		//0번째 인덱스와 1번째 인덱스 중 작은 값이 보스로 통일

		bool isConn = unionFind(costs[idx][0], costs[idx][1]);
		if (isConn) {
			cnt++;
			answer += costs[idx][2];
			if (cnt == n - 1)break;
		}
	}
	return answer;
}

 

두번째 코드 오답

논리는 모두 맞으나 마지막 for 조건문에서 n-1이 아니다. isConn 필터링으로 인해 n-1개 까지 실제 크루스칼알고리즘이 적용되지 않을 수 있기 때문이다. 이때는 isConn 조건문에 true 횟수가 n-1개 까지 진행하기위한 counting을 해야한다.

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


//크루스칼알고리즘
//1. 비용 기준 높은 순 정렬, 2. 유니온파인드, 3. n-1개 간선 까지의 비용 합
int org[101]; // 섬 100이하  , bool 타입으로 하면 segmentation 에러 발생 유의
bool comp(vector<int> base, vector<int> tar) {
    return base[2] < tar[2]; // std::sort 비교함수는 strict weak ordering 규칙을 따라야 해서 같을 때 반드시 false를 반환해야한다. 즉 <= 으로 true 시 런타임에러 발생 가능
}

int getParent(int now)
{
    if (org[now] == 0) return now;
    int ret = getParent(org[now]);
    org[now] = ret; // 최상위 부모노드의 자식들을 일렬로 배치
    return ret;
}
bool unionFind(int src1, int src2) {
    int parent1 = getParent(src1);
    int parent2 = getParent(src2);
    if (parent1 == parent2) return false;
    org[parent1] = parent2;
    return true;
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(), costs.end(), comp);
    for (int idx = 0; idx < n - 1; ++idx) { // costs.size()까지가 아닌 n-1 간선(n 정점 갯수 - 1)까지
        bool isConn = unionFind(costs[idx][0], costs[idx][1]);
        if (isConn) {
            answer += costs[idx][2];
        }
    }
    return answer;
}

 

 

첫번째 코드 오답

 

오답 이유: 간선이 중요하지 정점이 중요한게 아니다. visited로 간선여부가 고려되지 않는다. 

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;
/*
1. 비용 낮음->높음 순 정렬
2. visited 체크
*/
bool visited[101];
bool comp(vector<int> b, vector<int> tar){
    return b[2] <= tar[2];
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(), costs.end(), comp);
    for(int idx = 0; idx < costs.size(); ++idx){
        int src = costs[idx][0];
        int dst = costs[idx][1];
        if(visited[src] == 0 || visited[dst] == 0){
            cout<<src<< " "<< dst<<endl;
            visited[src] = 1;
            visited[dst] = 1;
            answer+=costs[idx][2];
        }
    }
    return answer;
}

 

 

 

개념 참고해보기

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

 

최소신장트리를 구하기 위한 크루스칼알고리즘은 그리디의 일종

 

최소신장트리 중 Prim 알고리즘 관련 영상 및 블로그

https://www.youtube.com/watch?v=y_25iKuQO5o

 

 

https://ansohxxn.github.io/algorithm/mst/

(C++) 최소 신장 트리 MST, 크루스칼 알고리즘, 프림 알고리즘