[백준] 16398번 행성 연결

문제: 16398번: 행성 연결

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

vector<int> nodes;

int find_set(int u) {
	if (nodes[u] == u)
		return u;
	return nodes[u] = find_set(nodes[u]);
}

void union_(int ur, int vr) {
	nodes[vr] = ur;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n; // 행성의 수
	cin >> n;
	nodes = vector<int>(n + 1); // 0번 인덱스 안 씀
	for (int i = 1; i < n + 1; i++)
		nodes[i] = i;


	// 행성 번호 1부터 시작하니까 n+1 만큼 크기 잡음..
	// 0번 인덱스 안 쓸 것..
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> minEdges;
	vector<vector<int>> linked(n + 1, vector<int>(n + 1));
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++) {
			cin >> linked[i][j];
			minEdges.push(make_pair(linked[i][j], make_pair(i, j)));
		}
	}

	int selectedCnt = 0;
	long long answer = 0;
	while (selectedCnt < n - 1) {
		pair<int, pair<int, int>> edges = minEdges.top();
		minEdges.pop();

		int ur = find_set(edges.second.first);
		int vr = find_set(edges.second.second);

		if (ur != vr) {
			union_(ur, vr);
			selectedCnt++;
			answer += edges.first;
		}
	}
	cout << answer << "\n";


	return 0;
}

 

분명히 맞게 푼 것 같았는데 막상 제출해보니 57%에서 틀렸었다. 이유가 대체 뭔가 해서 코드도 좀 수정해보고 했는데 문제 조건을 다시 보니 틀린 이유를 알 수 있었다.

 

각 정점 사이 연결선의 가중치의 최대 범위가 1억이고, 최대 n 의 범위가 1000 이었다. MST 알고리즘은 n-1 개의 간선을 찾을 때까지 반복을 하는 문제다. 이게 무엇을 의미하느냐? 최대의 상황을 가정해봤을 때 1억이 999개 있으면 int 범위를 벗어나는데 나는 answer 의 타입을 int 로 선언해서 틀린 것이었다..

 

항상 문제가 틀려서 왜 그런가 하고 보면 로직 자체가 문제인 경우도 많았지만 변수 타입 설정하는데에서도 자주... 실수를 한다. 문제 조건을 좀 더 자세히 읽는 버릇을 습관화 해야 하는데.. 문제 풀기에 급급하니까 자꾸 이런 어이없는 행위를 하는 듯.. 

 

앞으로는 제발 좀 주의하자!