BOJ(백준) 1833번 고속철도 설계하기

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

1833번: 고속철도 설계하기

문제를 읽어보면 최소 스패닝 트리 알고리즘으로 문제를 풀 수 있다는 것을 쉽게 떠올릴 수 있다. 

 

다만 기존에 연결되어 있는 간선들이 존재하기 때문에 최소 스패닝 트리 알고리즘을 적용하기 전에 우선 이미 존재하는 간선들을 통해 노드를 union한 뒤 disjoin set의 개수(즉, find를 했을 때 자기 자신이 부모인 노드의 개수)를 확인하고 그 수의 보다 하나 적은 개수만큼의 간선을 크루스칼 알고리즘을 통해 선택해주었다.

 

AC code

#include <bits/stdc++.h>
using namespace std;
int N,K,S,E,t,sol,cnt=-1;
vector<vector<int>> v;
vector<int> par;

int find(int a) {
	if(par[a]==a) return a;
	else return par[a]=find(par[a]);
}

void uni(int a,int b) {
	int pa=find(a),pb=find(b);
	if(pa>pb) swap(pa,pb);
	if(pa!=pb) par[pb]=pa;
}

int main()
{
	ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>N;
	par.resize(N+1);
	for(int i=1;i<=N;i++) par[i]=i;
	for(int i=1;i<=N;i++) for(int k=1;k<=N;k++) {
		cin>>t;
		if(i==k) continue;
		if(t<0) {
			sol-=t;
			uni(i,k);
		}
		else v.push_back({t,i,k});
	}
	sol>>=1;
	for(int i=1;i<=N;i++) if(par[i]==i) cnt++;
	sort(v.begin(),v.end());
	vector<pair<int,int>> l;
	for(int i=0;cnt;i++) {
		int pa=find(v[i][1]),pb=find(v[i][2]);
		if(pa!=pb) {
			uni(v[i][1],v[i][2]);
			l.push_back({v[i][1],v[i][2]});
			sol+=v[i][0];
			cnt--;
		}
	}
	cout<<sol<<" "<<l.size()<<"\n";
	for(auto i:l) cout<<i.first<<" "<<i.second<<"\n";
}