풀이

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int V, E;
vector<pair<long long, pair<int, int>>> edge;
int parents[1000];
int edgenum = 0;

int FindRoot(int x)
{
	if (x == parents[x])
		return x;
	return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y)
{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x == y)
		return;
	if (y > x)
		parents[y] = x;
	else
		parents[x] = y;
}





int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	for (int i = 0; i < 1000; i++)
	{
		parents[i] = i;
	}

	int N;
	long long res = 0;
	cin >> N;

	long long input;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++) {
			cin >> input;
			if ((i < j) && (i != j)) {
				edge.push_back({ input,{i,j} });
			}
		}

	}


	sort(edge.begin(), edge.end());

	for (int i = 0; i < edge.size(); i++)
	{
		if (FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
			continue;

		Merge(edge[i].second.first, edge[i].second.second);
		res += edge[i].first; 
		edgenum++;

		if (edgenum == N - 1)
			break;

	}
	cout << res<<'\n';
}

이 문제는 같은종류의 문제였던 최소스패닝트리의 전력난과 최소스패닝트리의 문제풀이만을 생각하고있다가 통수맞았습니다! 사실 통수가 아니라 제 지식과 응용의 문제이기도 하겠지만 이전까지 pair<int,pair<int,int>>를 잘 해오다가 이번 문제에서는 똑같이하면 안된다는것을 알았습니다.

위 사진은 각각 다르게 자료형을 가졌을때, sort하고 난 다음의 모습입니다.

vector<pair<long long,pair<int,int>>>로 하였을때는 sort가 cost의 오름차순으로 잘 정렬되어있지만, pair<long long,pair<int,int>> 를 했을 경우에는 중간부터 정렬이 어긋난것을 알 수가 있습니다.

이 원인은 알고보니 sort함수때문에 일어났는데요..제가 바보같이 pair<long long,pair<int,int>>를 했을 당시 sort를 (edge, edge+N)으로 두는 어마어마한 실수를 하였습니다. 분명 마지막 항목은 N이 아니고 그 배일텐데.. 제가  정말 앞에 푼 문제들만 생각하고 심각한 오류를 범했죠..

다행히 Vector<pair<long long,pair<int,int>>>를 했을때는 sort를 sort(edge.bigin(), edge.end())로 두었기에 제가 신경쓰지 않더라도 알아서 잘 정렬을 해주었습니다.

이 글을 쓰면서 다시 한번 쭉 검토해보니 통수가 아니라 정말 바보같은 실수네요! 오랜만에 문제를 풀어보았더니 이런 실수나 하고..부끄럽습니다! 열심히 이제부터 다시 공부해야겠네요 :D

끝만 잘 생각한다면 그냥 크루스칼 알고리즘 그대로 써도 될 정도의 최소스패닝트리 기본문제였습니다.

https://www.acmicpc.net/problem/16398