글 읽기 - 틀렸습니다..가 나옵니다.. 그리디하게 풀었습니다..ㅠ 도와주세요 제발.ㅠ

leekang9070 4년 전 0

Disjoint_Set을 이용하여 해결 하였으나... 75프로 정도에서 틀렸습니다가 나옵니다.. 도와주세요 ㅠㅠ

#include<iostream>
#include<vector>
using namespace std;
int getParent(int parent[], int x) {
	if (parent[x] == x) {
		return x;
	}
	else
	{
		return parent[x] = getParent(parent, parent[x]);
	}
}

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;
}

int nodesize;
int linesize;

class Line {
public:
	int start;
	int end;
	int cost;
};

vector<Line> v;
bool node[2000] = { false, };
bool finish() {

	for (int i = 1; i <= nodesize; i++) {
		if (node[i] == false) {
			return false;
		}
	}
	return true;
}
int result = 0;
void getResult(int parent[]) {

	while (finish() == false) {
		int cost = 987654321;
		int index = 0;
		for (int i = 0; i < v.size(); i++) {
			if (v[i].cost < cost) {
				index = i;
				cost = v[i].cost;
			}
		}

		if (getParent(parent, v[index].start) != getParent(parent, v[index].end)) {
			result += v[index].cost;
			node[v[index].start] = true;
			node[v[index].end] = true;
			unionParent(parent, v[index].start, v[index].end);
			v.erase(v.begin() + index);
		}
		else {
			v.erase(v.begin() + index);
		}

	}
	cout << result << endl;
}


int main() {
	int parent[2000];
	cin >> nodesize >> linesize;

	for (int i = 1; i <= nodesize; i++) {
		parent[i] = i;
	}
	Line a;
	for (int i = 0; i < linesize; i++) {
		cin >> a.start >> a.end >> a.cost;
		v.push_back(a);
	}
	if (nodesize == 1) {
		cout << 0 << endl;
	}
	else
	{
		getResult(parent);
	}
}