[백준OJ] 18769번 그리드 네트워크

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

18769번: 그리드 네트워크

---

 

-풀이-

파인드-유니온을 이용해서 그래프이론중, MST를 이용하여 풀었다.

먼저 edge들을 모두 받은뒤, 가중치값을 기준으로 오름차순정렬을 해준다.

그런뒤 모든 구역을 자신한정으로 초기설정을 해준뒤, 정렬된 edge를 탐색하며, edge로 연결된 두 정점이 같은 구역에 있지 않다면, 가중치의 값을 더해주고, 두 정점을 union_parent를 이용하여 같은 구역으로 합쳐준다.

이렇게 모든 edge들을 탐색하면 MST가 완성이 되고, 최소설치비용을 구할 수 있다.

 

-시간복잡도-

초기 셋팅 (parent배열 초기화 및 입력) = O(RC)

edge벡터 정렬 = 원소의 개수가 (R-1)*C + R*(C-1)개 이므로, 대략 2RC개가 된다. 따라서 정렬에 걸리는 시간은 O(RC log RC) 가 된다.

MST알고리즘은 경로를 압축한 FIND 알고리즘으로 인해O(1)시간이 걸리고, UNION_PARENT에 O(1) 이 걸리므로, 원소의 개수만큼 시간이 든다. 따라서 O(RC)가 된다.

따라서 최종 시간복잡도는 O(RClogRC)가 된다.

 

-코드-

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

pair<int,int> parent[501][501];
vector<pair<pair<pair<int,int>, pair<int,int>>,int>> edge;
int r, c,t;

bool compare(pair<pair<pair<int, int>, pair<int, int>>, int> a, pair<pair<pair<int, int>, pair<int, int>>, int> b) {
	return a.second < b.second;
}

pair<int,int> find(pair<int,int> a) {
	if (a == parent[a.first][a.second]) {
		return a;
	}
	else {
		return parent[a.first][a.second]=find(parent[a.first][a.second]);
	}
}

void union_parent(pair<int,int> a, pair<int, int> b) {
	a = find(a);
	b = find(b);

	if (a < b) {
		parent[b.first][b.second] = a;
	}
	else {
		parent[a.first][a.second] = b;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> t;
	while (t--) {
		cin >> r >> c;
		edge.clear();
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				parent[i][j] = { i,j };
			}
		}

		for (int i = 1; i <= r; i++) {
			for (int j = 1; j < c; j++) {
				int cost;
				cin >> cost;
				edge.push_back({ {{i,j},{i,j + 1}},cost });
			}
		}

		for (int i = 1; i < r; i++) {
			for (int j = 1; j <= c; j++) {
				int cost;
				cin >> cost;
				edge.push_back({ {{i,j},{i + 1,j}},cost });
			}
		}

		sort(edge.begin(), edge.end(), compare);
		int total = 0;
		for (int i = 0; i < edge.size(); i++) {
			pair<int, int> a, b;
			int cost;
			a = edge[i].first.first;
			b = edge[i].first.second;
			cost = edge[i].second;
			if (find(a) != find(b)) {
				union_parent(a, b);
				total += cost;
			}
		}
		cout << total << "\n";
	}

	return 0;
}