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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

모든 섬을 연결하라는 의미는 결국 MST를 만들라는 말과 같다.

아래의 코드에서는 입력으로 들어온 costs 벡터를 edges 벡터에 저장하고 kruskal 알고리즘을 사용해 MST를 생성해서 해결했다.

코드

C++

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int parent[101];
	vector<pair<int, pair<int, int>>> edges;
	int find(int x) {
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]);
	}
	void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
	}
	int kruskal() {
	sort(edges.begin(), edges.end());
	int sum = 0;
	for (int i = 0; i < edges.size(); i++) {
	int a = edges[i].second.first;
	int b = edges[i].second.second;
	int cost = edges[i].first;
	if (find(a) == find(b)) continue;
	merge(a, b);
	sum += cost;
	}
	return sum;
	}
	int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	for (auto i : costs) {
	edges.push_back({ i[2], {i[0], i[1]} });
	}
	for (int i = 1; i <= n; i++) parent[i] = i;
	answer = kruskal();
	return answer;
	}

view raw 섬 연결하기.cpp hosted with ❤ by GitHub