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

링크 

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

 

풀이

n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 최소 비용을 찾아야 한다.

 

방법을 생각해 보면 섬과 섬사이의 비용이 가장 작은순서대로 정렬하여 연결하면 되지만 이미 연결된 섬을 다시 연결 하면 안되고 건너 뛰어야 된다는 생각을 해볼 수 있습니다.

 

이때 필요한 알고리즘은 크루스칼(Kruskal)알고리즘을 이용할 수 있습니다.

크루스칼 알고리즘은 탐욕적인 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 방법입니다.

 

1. 최소비용으로 연결된 노드를 찾기 -> priority_queue를 이용

2. 섬과 섬이 이미 연결되어 있는지 확인 -> union, find를 이용

 

각각 연결된 섬에서 값이 작은 순서대로 정렬되도록 pq에 추가 한 후

연결된 값의 최소값을 pop 하면서 union, find를 이용하여 이미 연결된 섬인지 확인하고

연결되지 않았으면 섬을 연결하고 연결 되어있다면 연결하지 않습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>

#define INF 2e9
#define SIZE 110

using namespace std;

typedef long long int ll;

typedef struct Data {
	int node1, node2, cost;
}Data;

int parrent[SIZE];
priority_queue<Data, vector<Data>, cmp> pq;

void init() {
	for (int i = 0; i < SIZE; i++) {
		parrent[i] = i;
	}
}

struct cmp {
	bool operator()(Data d1, Data d2) {
		return d1.cost > d2.cost;
	}
};

int _find(int a) {
	if (parrent[a] == a)
		return a;
	else
		return parrent[a] = _find(parrent[a]);
}

void _union(int a, int b) {
	int aRoot = _find(a);
	int bRoot = _find(b);

	if (aRoot == bRoot)
		return;

	parrent[bRoot] = aRoot;
}

int solution(int n, vector<vector<int>> costs) {
	init();
	int c_size = costs.size();
	for (int i = 0; i < c_size; i++) {
		Data n;
		n.node1 = costs[i][0];
		n.node2 = costs[i][1];
		n.cost = costs[i][2];
		pq.push(n);
	}

	int answer = 0;
	while (!pq.empty()) {
		Data here = pq.top();
		pq.pop();

		if (_find(here.node1) != _find(here.node2)) {
			_union(here.node1, here.node2);
			answer += here.cost;
		}
	}
	
	return answer;

}