[Programmers] Lv3. 섬 연결하기

• 이 글은 c++로 풀이를 작성하였습니다.

문제

예시

---

풀이

	#include <string>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	// 크루스칼 알고리즘으로 해결
	// 엣지 표현하기 위한 클래스
	class Edge{
	public:
	int s,e,c;
	Edge(int s,int e,int c):s(s),e(e),c(c){};
	};
	// 엣지 최소 비용순으로 정렬
	bool cmp(Edge a, Edge b){
	return a.c < b.c;
	}
	// union-find에서 부모노드 찾기
	int getParent(int parent[], int x){
	if(x == parent[x]){return x;}
	return parent[x] = getParent(parent,parent[x]);
	}
	// union-find 부모노드 합치기
	void unionParent(int parent[], int a, int b){
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a<b){
	parent[b] = a;
	}
	else{
	parent[a] = b;
	}
	}
	// union-find 부모노드 같은지 찾기
	int findParent(int parent[], int a, int b){
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a == b)return 1;
	else return 0;
	}
	int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	int check[100];
	for(int i=0;i<100;i++){
	check[i] = i;
	}
	// 각 정점을 vec에 넣고 비용이 적은 간선부터 정렬한다.
	vector<Edge> vec;
	for(int i=0;i<costs.size();i++){
	Edge e = Edge(costs[i][0],costs[i][1],costs[i][2]);
	vec.push_back(e);
	}
	sort(vec.begin(),vec.end(),cmp);
	// 각 노드들 관계가 사이클이 없으면 추가한다.
	for(int i=0;i<vec.size();i++){
	if(!findParent(check, vec[i].s, vec[i].e)){
	unionParent(check, vec[i].s, vec[i].e);
	answer+=vec[i].c;
	}
	}
	return answer;
	}

view raw Programmers Lv3.land connection.cpp hosted with ❤ by GitHub

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.