[BOJ/Gold 3] 백준 1833 고속철도 설계하기(C++)

문제 링크

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

1833번: 고속철도 설계하기

 

문제

N(1≤N≤200)개의 도시로 이루어진 나라가 있다. 이 도시들 사이를 다니는 고속철도망을 만들어 도시 간의 이동을 편하게 하려고 한다. 단, 고속철도망을 만든 후에 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있게 하려고 한다.

시범 사업으로 몇 개의 도시 사이에 고속철도가 설치되었는데 그 결과가 매우 좋아 국가에서는 이 사업을 완성하기로 하였다. 이제 당신은 몇 개의 도시 사이에 고속철도를 추가로 설치하여, 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있게 하려고 한다.

그러나 이 사업은 워낙 돈이 많이 드는 사업이기 때문에, 이 사업에 드는 총 비용을 최소화 하려고 한다. 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어졌을 때, 총 비용을 최소로 하여 사업을 완성하여 보자.

예를 들어 아래와 같은 경우를 보자.

현재 1번 도시와 2번 도시, 2번 도시와 4번 도시, 1번 도시와 4번 도시 사이에 고속철도가 설치되어 있다. 각각의 수는 두 도시 사이에 고속철도를 설치하는데 드는 비용을 나타낸다. 예를 들어 2번 도시와 3번 도시 사이에 고속철도를 설치하면 10만큼의 비용이 든다는 것을 의미한다. 위의 그림에 나타나지 않은 비용은 다 1,000이라고 하자.

위와 같은 경우에는 2, 3번 도시 사이에 고속철도를 설치하고, 3, 5번 도시 사이에 고속철도를 설치하면, 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 갈 수 있으며, 이 경우는 10+20+30+10+10=80만큼의 총 비용으로 사업을 완성할 수 있다. 10+20+30은 이미 설치된 고속도로에 대한 비용을 의미한다.

2, 4번 도시를 연결하는 고속철도가 없더라도 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있지만, 이미 설치되어 있는 고속철도를 돈을 들여가며 파괴할 필요가 없으므로, 이런 건 생각하지 않기로 한다.

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음수라면, 그 두 도시 사이에 이미 고속철도가 설치되어 있는 경우를 의미한다.

출력

첫째 줄에 두 정수 C, M를 출력한다. C는 고속철도망을 설치하는데 든 총 비용이며, M은 새로이 설치한 고속철도의 개수이다. 다음 M개의 줄에는 새로 고속철도가 설치된 두 도시번호를 출력한다. 우리가 최소화 하려는 것은 C이다.

예제 입력 1

5
   0  -10 1000  -20 1000
 -10    0   10  -30 1000
1000   10    0   30   10
 -20  -30   30    0   20
1000 1000   10   20    0

예제 출력 1

80 2
2 3
3 5

알고리즘 분류

• 크루스칼 알고리즘

풀이

이미 연결되어 있는 고속철도(가중치가 음수)라면 입력받으면서 미리 연결한다. 정점과 정점 사이에 고속철도를 놓을 때 필요한 비용(가중치가 양수)은 간선 벡터(Edge)에 push한다.

그리고 크루스칼 알고리즘을 사용하여, 최소 스패닝 트리를 만들어 최소의 비용(answerC)을 구하고, 최소 스패닝 트리를 만들기 위해 추가로 필요한 간선의 개수(answerM)와 간선의 정보(answerV)를 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Start, End, Cost;
};

int N;
vector<INFO> Edge;
int Parent[MAX];
int answerC = 0;
int answerM = 0;
vector<pair<int, int> > answerV;

void Init() {
	for (int i = 1; i <= N; i++) {
		Parent[i] = i;
	}
}

bool Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX < PY) {
		Parent[PY] = PX;
	}
	else {
		Parent[PX] = PY;
	}
}

bool isConnected() {
	for (int i = 2; i <= N; i++) {
		if (Find(1) != Find(i)) {
			return false;
		}
	}
	return true;
}

void Input() {
	cin >> N;
	Init();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int C;
			cin >> C;
			if (i < j) {
				if (C < 0) {
					Union(i, j);
					answerC -= C;
				}
				else {
					Edge.push_back({ i,j,C });
				}
			}
		}
	}
}

void Settings() {
	sort(Edge.begin(), Edge.end(), Comp);
	for (int i = 0; i < Edge.size(); i++) {
		int S = Edge[i].Start;
		int E = Edge[i].End;
		int C = Edge[i].Cost;
		if (Find(S) != Find(E)) {
			Union(S, E);
			answerC += C;
			answerM++;
			answerV.push_back(make_pair(S, E));
		}
	}
}

void Find_Answer() {
	cout << answerC << " " << answerM << "\n";
	for (int i = 0; i < answerV.size(); i++) {
		cout << answerV[i].first << " " << answerV[i].second << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}