[백준/BOJ] 2463번 비용

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

2463번: 비용

흥미롭게 시작했다가 long long 때문에 매우 고통스러웠던 문제.

분명 증명까지 해서 답이 확실한데 자꾸 틀리길래 중간에 long long 과 int 형이 변환되면서 답이 달라졌을것같아서

가중치(cost)부분을 모두 long long 으로 만드니 맞았다.

2가지 방법으로 풀었는데,

첫번째 방법은 답은 정확하게 구하나 시간초과가 나는 아이디어고

두번째 방법은 반성하며 푼 한번만 보면되는 아이디어다. 기록을 위해 모두 남겨봐야겠다.

 

1. 시간초과 아이디어.

문제를 읽고 구하는 방법을 따져 보니 그래프가 분리가되는 상황에서 g1 과 g2 에 속한 노드들의 서로를 향한

cost를 구할 수 있다는 것을 알게되어, 제일 작은 cost를 가지는 엣지부터 제거해 나가며(cost는 누적되어진다.)

그래프가 분리가 되는지 아니면 엣지만 지워진 건지를 확인해 분리되었으면 누적되어온 cost를

(g1노드수 x g2 노드수)의 값과 곱했다. 

ex) 1번노드가 혼자 분리 / 나머지 2번부터 6번까지 노드는 한묶음 : 1x6=6

ex) 1번노드와 2번 노드가 같이묶여서 분리 / 나머지 3번부터 6번까지 노드는 한묶음 : 2x4=8

 

따라서 엣지를 지울때마다 그래프 분리 확인을 위해 매번 bfs를 탐색했더니 당연히 터졌다.

(사실 풀면서도 터질 줄 알았다ㅜㅜ)

 

 

<틀린 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<map>
using namespace std;
vector<vector<pair<int, int>>>adj;
vector<pair<int,int>>::iterator iter;
long long MAX = 1e9;
int bfs(int start) {
	int ck[100005] = { false };
	int nodenum = 1;
	queue<int>q;
	q.push(start);
	ck[start] =true;
	while (!q.empty()) {
		int pre = q.front();
		q.pop();
		for (int i = 0; i < adj[pre].size(); i++) {
			if (!ck[adj[pre][i].first]) {
				ck[adj[pre][i].first] = true;
				q.push(adj[pre][i].first);
				nodenum++;
			}
		}
	}
	return nodenum;
}
int main(void) {
	int N, M;
	scanf("%d %d", &N, &M);

	adj.resize(N + 1);
	priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>,greater<pair<long long, pair<int, int>>>>pq;
	for (int i = 0; i < M; i++) {
		int x, y, z;
		scanf(" %d %d %d", &x, &y, &z);
		adj[x].push_back({ y,z });
		adj[y].push_back({ x,z });
		if (x > y)swap(x, y);
		pq.push({ z,{x,y} });
	}
	long long del = 0;
	long long result = 0;
	while (!pq.empty()) {
		//memset(ck, 0, sizeof(ck));
		int prex = pq.top().second.first;
		int prey = pq.top().second.second;
		long long predel = pq.top().first;
		del = (del + predel) % MAX;
		pq.pop();
		int before = bfs(prex);
		//엣지 지우기
		for (int i = 0; i < adj[prex].size(); i++) {
			iter = adj[prex].begin();
			if (adj[prex][i].first == prey) adj[prex].erase(iter+i);
		}
		for (int i = 0; i < adj[prey].size(); i++) {
			iter = adj[prey].begin();
			if (adj[prey][i].first == prex)adj[prey].erase(iter+i);
		}

		//돌면서 끊어졋나 확인

		int after = bfs(prex); //끊어졌다면 다른 묶음과 확인.

		if (before != after) {
			result += ((before - after)*(before - (before - after))*del) % MAX;
		}

	}

	printf("%lld\n", result);
	



	return 0;
}

 

 

 

 

2. 정답 아이디어

풀다 지쳐 잠들때 쯤 생각난건데, 작은 것부터 보지말고 큰엣지 부터 보면 되지않을까에서 시작한다.

큰 것부터 보기 시작하면 노드가 그래프를 형성하는 방향으로 보는 것 인데,

여기서는 노드수가 누적이 된다. 왜냐면 큰 엣지일수록 나중에 없어질 것이고 그러면 해당 노드들은 작은 엣지의 양까지 합쳐져서 전체 cost값이 구해지기 때문이다. 

음... 직접 계산하다보면 규칙이 보인다.....(글로 설명하는 ....설명의 한계)

따라서 이미 같은 묶음에 있는 노드 2개를 연결할 것인지 아니면 다른 묶음의 노드를 연결할 것인지를 판단해서 

다른 묶음이었을때는 1번아이디어와 마찬가지로 노드수를 곱해서 누적 노드수에 더하고, 같을때는 누적 노드 수는 0이다.

묶음을 확인 하는 방법으로 유니온-파인드 방식을 썼다.

 

 

 

 

 

 

 

 

 

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<map>
using namespace std;
int MAX = 1e9;
int parent[100005] = { 0 };
long long groupnum[100005];

int find(int node) {
	if (parent[node] == node)return node;
	return parent[node] = find(parent[node]);
}

long long merge(int be, int af) {
	be = find(be);
	af = find(af);
	
	if (be == af) {
		return 0;
	}
	else { 
		parent[af] = be;
		long long re= (groupnum[be] * groupnum[af])%MAX;
		groupnum[be] += groupnum[af];
		groupnum[af] = groupnum[be];
		
		return re;
	}
}

int main(void) {
	int N, M;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= 100001; i++) {
		groupnum[i] = 1;
		parent[i] = i;
	}
	priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>>pq;
	for (int i = 0; i < M; i++) {
		int x, y;
		long long z;
		scanf(" %d %d %lld", &x, &y, &z);
		if (x > y)swap(x, y);
		pq.push({ z,{x,y} });
	}
	long long result = 0;
	long long prenode = 0;
	while (!pq.empty()) {
		int be = pq.top().second.first;
		int af = pq.top().second.second;
		long long cost = pq.top().first;
		pq.pop();
		prenode += merge(be, af);

		result = (result+(prenode*cost)%MAX)%MAX;
	}
	printf("%lld\n", result);
	return 0;
}