[BOJ/Gold 4] 백준 18769 그리드 네트워크(C++)

문제 링크

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

18769번: 그리드 네트워크

 

문제

재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통신망에 있는 임의의 두 서버는 통신을 할 수 있어야 한다. 두 서버가 직접 연결되어 있지 않아도 다른 서버를 통해서 통신을 할 수 있어도 된다.

서버는 행의 개수가 R개, 열의 개수가 C개인 격자로 나타낼 수 있다. 상하좌우로 인접한 서버 사이에는 직접 통신망을 설치할 수 있다. 직접 통신망을 설치하는 비용은 1, 2, 3, 4중 하나이다. 직접 통신망의 비용에는 흥미로운 성질이 하나 있는데, 한 서버 A와 인접한 B, C가 있을 때, A와 B 사이에 통신망을 설치하는 비용과 A와 C 사이에 설치하는 비용이 같은 경우는 없다는 것이다.

그림 (a)와 같은 그리드 네트워크의 경우 다섯 개의 통신망을 설치해서 임의의 두 서버가 통신할 수 있게 만들 수 있고, 최소 비용은 9이다. 최소가 되게 설치하는 방법은 총 두 가지가 있고, 그림 (c)와 그림 (d)에 빨간색으로 표시된 통신망을 설치하면 된다.그림 (a)는 총 여섯 대의 서버가 있고, 각 서버 사이에 설치할 수 있는 통신망의 비용이 나와있는 그림이다. 그림 (b)는 (1, 2)와 (2, 2)에 있는 서버에서 비용이 같은 통신망이 두 개 있기 때문에, 입력으로 주어지지 않는 형태이다.

그리드 네트워크와 통신망의 설치 비용이 주어졌을 때, 임의의 두 서버가 통신할 수 있도록 하기 위한 최소 비용을 구해보자.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 R과 C가 공백으로 구분되어 주어진다. 다음 R개의 줄에 걸쳐서 각 줄에 C-1개의 정수가 주어지는데, 이 정수는 각 행에 놓인 C개의 서버에서 좌우로 연결하는 통신망을 설치하는 비용을 나타낸다. 다음 R-1개의 줄에 걸쳐서 각 줄에 C개의 정수가 주어지는데, 이 정수는 i번째 행과 i+1번째 행에 놓인 C개의 서버를 상하로 연결하는 통신망을 설치하는 비용을 나타낸다.

출력

각 테스트 케이스마다 최소 비용을 한 줄에 하나씩 출력한다.

제한

• 1 ≤ T ≤ 10
• 2 ≤ R, C ≤ 500
• 1 ≤ 각 회선의 설치 비용 ≤ 4

서브태스크 1 (4점)

• 2 ≤ R, C ≤ 7
• 그리드 네트워크의 간선 개수가 20개 이하이다.

서브태스크 2 (9점)

• 2 ≤ R, C ≤ 500

예제 입력 1

3
2 3
1 3
3 1
2 4 2
2 2
1
1
2 2
3 3
1 2
1 4
4 3
2 3 3
3 2 1

예제 출력 1

9
4
15

• 테스트 케이스 1: 문제의 본문에서 다룬 예시이다.
• 테스트 케이스 2: 두 가지 방법이 존재하며, 비용이 2인 회선 둘 중 하나만 사용해야 최소 비용이다.
• 테스트 케이스 3: 두 가지 방법이 존재한다.

알고리즘 분류

• 크루스칼 알고리즘

풀이

주어진 정보로 간선을 만들고, 가중치 순으로 오름차순 정렬한다. 그리고 최소 스패닝 트리를 만들고 가중치의 합의 최솟값을 출력한다.

이 때 서버는 2차원 배열로 구성되어 있지만, (i * C) + j를 이용하여 1차원 배열로 취급한다.

코드

#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 250005
#define LL long long
#define INF 1e9

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

int T, R, C;
vector<INFO> Edge;
int Parent[MAX];
int answer;

void Init() {
	for (int i = 0; i < (R * C); i++) {
		Parent[i] = i;
	}
	Edge.clear();
	answer = 0;
}

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 Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

void Settings() {
	for (int i = 0; i < Edge.size(); i++) {
		int S = Edge[i].Start;
		int E = Edge[i].End;
		int Cost = Edge[i].Cost;
		if (Find(S) != Find(E)) {
			Union(S, E);
			answer += Cost;
		}
	}
}

void Find_Answer() {
	cout << answer << "\n";
}

void Input() {
	cin >> T;
	while (T--) {
		cin >> R >> C;
		Init();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C - 1; j++) {
				int Cost;
				cin >> Cost;
				int S = (i * C) + j;
				int E = (i * C) + j + 1;
				Edge.push_back({ S,E,Cost });
			}
		}
		for (int i = 0; i < (R - 1); i++) {
			for (int j = 0; j < C; j++) {
				int Cost;
				cin >> Cost;
				int S = (i * C) + j;
				int E = ((i + 1) * C) + j;
				Edge.push_back({ S,E,Cost });
			}
		}
		sort(Edge.begin(), Edge.end(), Comp);
		Settings();
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}