[BOJ] 10021 : Watering the Fields

문제 : https://www.acmicpc.net/problem/10021

---

MST Graph Prim

 N개의 노드가 존재하고, a 노드에서 b 노드로 가는 간선이 존재하려면, 거리가 C 이상이여야 됩니다. 우리는 모든 노드들이 서로 연결되어있는 상태를 최소 비용으로 만들고 싶으므로, MST를 만들면 됩니다.

 MST 알고리즘은 대표적으로 Prim, Kruskal 2개가 있는데 이 문제는 간선이 굉장히 많이 존재할 수 있는 밀집 그래프 문제이므로 Kruskal로 MST를 구하면 시간초과를 직면하게 되고, Prim 알고리즘을 사용해야된다.

 

1) 모든 노드를 순회하며 거리를 계산하고, 거리가 C 이상이면 graph 에 간선을 만들어준다.

( 간선은 양방향 )

2) Prim 알고리즘을 통해 MST를 구한다.

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

const int INF = 1000000001;

int N, C;
int graph[2000][2000];
pair<int, int> point[2000];
int dist[2000];
bool selected[2000];

int getDist(int i, int j) {
	return (int)pow(point[i].first - point[j].first, 2) + (int)pow(point[i].second - point[j].second, 2);
}

int get_min_vertex() {
	int v;
	for (int i = 0; i < N; i++) {
		if (!selected[i]) {
			v = i;
			break;
		}
	}
	for (int i = 0; i < N; i++)
		if (!selected[i] && (dist[i] < dist[v])) v = i;
	return v;
}

int prim(int s) {
	for (int i = 0; i < N; i++)
		dist[i] = INF;
	dist[s] = 0;
	for (int i = 0; i < N; i++) {
		int u = get_min_vertex();
		selected[u] = 1;
		if (dist[u] == INF) return -1;
		for (int j = 0; j < N; j++)
			if (graph[u][j] != INF && !selected[j] && graph[u][j] < dist[j])
				dist[j] = graph[u][j];
	}
    int ans = 0;
    for(int i = 0; i < N; i++) ans += dist[i];
    return ans;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	// i <--> j 의 모든 edge를 구하고, MST를 구하면 된다.
	cin >> N >> C;
	for (int i = 0; i < N; i++)
		cin >> point[i].first >> point[i].second;

	// 프림으로 해보자.
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++) {
			int dist = getDist(i, j);
			if (C <= dist) graph[i][j] = graph[j][i] = dist;
			else graph[i][j] = graph[j][i] = INF;
		}
    cout << prim(0) << '\n';
    
	return 0;
	
}

---