[D4] SWEA 1251번 [S/W 문제해결 응용] 4일차 - 하나로 MST, 최소 스패닝 트리

 

리뷰

 

SW Expert Academy

모든 섬을 연결하는 해저터널의 최소 길이를 구하는 문제, 크루스칼 MST문제의 기본형이다.

간선의 가중치를 직접 구해야 하며 소숫점이 들어오기 때문에 형변환이 중요해 보인다.

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장하기 위한 변수
• n : 섬의 개수를 저장하기 위한 변수
• e : 환경 부담 세율을 저장하기 위한 변수
• nodes : 유니온 파인드를 통해 그룹을 짓기 위한 정수형 배열
• Pos : x, y 위치 좌표 정보를 정의하기 위한 구조체
• poses : 각 섬의 x, y 좌표를 저장하기 위한 Pos타입의 배열
• Edge : 간선 정보를 정의하기 위한 구조체, 시작 및 도착 노드와 가중치 오름차순으로 정렬하여 정의한다.

 

함수

1. getdist

double getdist(const Pos& pos1, const Pos& pos2)

 

두 섬을 잇는 해저터널 건설 시 발생하는 최소 환경 부담금을 구하는 함수

1. 두 섬의 위치 정보를 매개변수로 입력 받아준다.
2. 두 섬 사이의 거리를 제곱한 값에 e를 곱한 값을 리턴해 준다.

 

2. Find

int Find(int a)

 

현재 섬이 어떤 그룹에 속해있는지 확인하기 위한 함수

1. 매개변수로 그룹을 확인하고자 하는 섬 번호를 a로 입력 받는다.
2. 기저조건으로 a가 속한 그룹이 자기자신일 경우 a를 리턴해 준다.
3. 아닐 경우 Find에 자기가 속한 그룹을 매개변수로 전달하여 재귀탐색을 진행해 준다.
4. 자신이 속한 그룹을 위 Find의 리턴값으로 갱신하고 그 값을 리턴하며 재귀를 빠져나와 준다.

 

3. Union

bool Union(int a, int b)

 

두 섬의 그룹화를 진행하기 위한 함수

1. 두개의 섬 번호를 각각 a, b로 입력 받아준다.
2. Find함수에 a, b각각을 매개변수로 전달하여 속한 그룹 A, B로 값을 받아준다.
3. 만약 A와 B가 동일할 경우 이미 동일 그룹인 상태이므로 false를 리턴해 준다.
4. 둘이 다를 경우 B가 속한 그룹을 A로 변경해 준다.
5. 그룹화를 진행했으므로 true를 리턴해 준다.

 

문제풀이

1. t를 입력 받아주고, t번의 테스트케이스를 진행해 준다.
2. 각 테스트 케이스 마다 섬의 개수를 n에 입력 받아준다.
3. n개의 섬에 대한 좌표 x, y를 poses배열에 입력 받아준다.
4. e값을 입력 받아주고 Edge타입의 벡터 edges를 초기화 해준다.
5. 브루트포스 알고리즘을 통해 각각 섬에 대한 모든 간선을 edges벡터에 추가해 준다.
6. sort메서드를 통해 edges벡터를 간선의 길이를 기준으로 오름차순으로 정렬해 준다.
7. 유니온 파인드를 위해 n개의 섬을 nodes배열에서 각각 자신을 값으로 같게끔 초기화 해준다.
8. 부동 소숫점형의 sum변수를 0으로 초기화 해준다.
9. edges벡터를 순회하며 두 섬이 연결 가능하면 연결 후 sum에 간선의 가중치를 더해준다.
10. 모든 간선을 순회한 후에 sum에 저장된 값을 반올림 후 long long타입으로 변환하여 출력해 준다.
11. 각 테스트 케이스 마다 위 로직을 반복하여 수행해 준다.

 

트러블슈팅

• round를 하지 않고 바로 long long타입으로 변환 후 출력하였다가 버림 처리가 되어 최초 AC를 받지 못했다.

 

참고 사항

• x, y좌표가 연달아 주어지는게 아니고 x좌표 먼저, 그 다음 y좌표를 받게끔 입력이 주어진다.

 

정답 코드

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

int t, n;
double e;
int nodes[1001];
struct Pos {
	int x, y;
};
Pos poses[1001];
struct Edge {
	int sn, dn;
	double w;
	bool operator<(const Edge& other) const {
		if (w == other.w) return sn < other.sn;
		return w < other.w;
	}
};

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

bool Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return false;
	nodes[B] = A;
	return true;
}

double getdist(const Pos& pos1, const Pos& pos2) {
	return e * (pow(abs(pos1.x - pos2.x), 2) + pow(abs(pos1.y - pos2.y), 2));
}

int main() {
	cin >> t;
	for (int tc = 1; tc <= t; ++tc) {
		cin >> n;
		for (int i = 1; i <= n; ++i) cin >> poses[i].x;
		for (int i = 1; i <= n; ++i) cin >> poses[i].y;

		cin >> e;
		vector<Edge> edges;
		for (int i = 1; i < n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				const Pos& pos1 = poses[i], pos2 = poses[j];
				double dist = getdist(pos1, pos2);
				edges.push_back({ i, j, dist });
			}
		}
		sort(edges.begin(), edges.end());

		for (int i = 1; i <= n; ++i) nodes[i] = i;
		double sum = 0;
		for (const Edge& edge : edges) {
			int A = edge.sn, B = edge.dn;
			double w = edge.w;
			if (Union(A, B)) sum += w;
		}
		cout << "#" << tc << " " << (long long)round(sum) << "\n";
	}
}