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

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

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

입출력 예

ncostsreturn

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

그리디 문제로 나온 그래프 문제이다.

나는 크러스칼 알고리즘을 이용해서 풀었다.

 

크러스칼 알고리즘은 그래프에서 가중치가 가장 낮은 다리를 차례대로 고르는 알고리즘이다. 

주의할 점은 가중치가 낮더라도 사이클을 생성하면 골라선 안된다. 

예를들어 5개의 섬이 있을때 두개의 섬이 서로 연결되고 세개의 섬이 사이클을 이루면 모든 섬에 다리가 지어지긴 하지만 사이클에 속하는 섬들과 그렇지 않은 섬들은 연결되지 않는다.

이 사이클이 생기는지 확인하는 방법은 disjoint-set 알고리즘을 활용한다. union-find로 잘 알려진 알고리즘인데 내 블로그에 포스트를 올린 적이 있으니 기억이 안난다면 확인해보자.

https://chosh95.tistory.com/111?category=835072

disjoint-set (Union-Find)

union-find만 활용하고 충분히 해결할 수 있지만 왠지 그래프 문제는 priority queue를 쓰고 싶어서 활용해봤다.

node를 struct로 만들고, 큐를 선언한다. cmp 구조체도 함께 선언해서 cost가 가장 낮은 다리부터 뽑도록 한다.

 

큐에 노드가 있는 동안은 계속해서 내용물을 추출하며 x와 y의 parent를 구해서 둘이 사이클을 이루는지 확인한다.

부모가 같다면 사이클을 이룬다는 뜻이다. 

사이클을 이루지 않는다면 값이 더 큰 노드를 부모로 갖도록 한 후 answer에 가중치를 더해주자.

큐가 빌때까지 반복하면 답을 구할 수 있다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EC%84%AC%20%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0.cpp

chosh95/STUDY

C++ 코드

#include <string>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
	int x;
	int y;
	int cost;
	node(int x, int y, int cost) :x(x), y(y), cost(cost) {}
};

struct cmp {
	bool operator()(node a, node b) {
		return a.cost > b.cost;
	}
};

int visit[101];
int parent[101];
int find(int n) {
	if (parent[n] == n) return n;
	return parent[n] = find(parent[n]);
}

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	priority_queue<node, vector<node>, cmp> q;
	for (int i = 0; i < costs.size(); i++)
		q.push(node(costs[i][0], costs[i][1], costs[i][2]));

	for (int i = 0; i < n; i++) parent[i] = i;

	while (!q.empty()) {
		int x = find(q.top().x);
		int y = find(q.top().y);
		int cost = q.top().cost;
		q.pop();
		if (x == y) continue;
		if (x > y) parent[y] = x;
		else parent[x] = y;
		answer += cost;
	}
	return answer;
}

int main()
{
	cout << solution(4, { {0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8} });
}