SWEA 1251 : 하나로[D4] (c++)

* 문제 링크 :

https://swexpertacademy.com/main/main.do -> 로그인 -> 문제은행 -> '1251' or '하나로' 검색

 

** 문제 풀이 방법

Goal) N개의 섬 최소 길이로 모두 연결   - 1<=N<=1,000   - 0<= X,Y<= 1,000,000   - 0<= E <= 1 <순서> 1) 섬 좌표(X, Y) 입력 받기 2) i 도시에서 j 도시 거리 행렬 만들어 놓기(매번 연산 x) 3) Kruscal 알고리즘 사용

 

*** 코드

#include <stdio.h>
#include <vector>
#include <algorithm>

#define SQUARE(X) (X*X)
#define MAX_NUM 10010
typedef long long ll;

struct edge {
	int start;
	int end;
	ll distance;
};
struct P {
	int x;
	int y;
};

using namespace std;

int N;											// 도시 수
int parent[MAX_NUM];
P map[MAX_NUM];								    // 섬 좌표 입력
vector<edge> dist;								// i -> j 섬 이동 거리 계산 벡터
double E, cost;

bool cmp(edge a, edge b) {
	return a.distance < b.distance;
}

void init() {
	scanf("%d ", &N);
	dist.clear();								// 벡터 초기화	
}

void input() {
	init();
	for (int i = 0; i < N; i++) {
		parent[i] = i;							// 부모 배열 초기화
	}

	int x, y;
	for (int i = 0; i < N; i++) {
		scanf("%d ", &x);
		map[i].x = x;
	}
	for (int i = 0; i < N; i++) {
		scanf("%d ", &y);
		map[i].y = y;
	}

	scanf("%lf ", &E);
}

void setDistance() {
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			ll x_gap = map[i].x - map[j].x;
			ll y_gap = map[i].y - map[j].y;
			ll X = SQUARE(x_gap);
			ll Y = SQUARE(y_gap);
			dist.emplace_back(edge{ i, j, X + Y });
			//dist.push_back(edge{ i, j, X + Y });
		}
	}
	sort(dist.begin(), dist.end(), cmp);            // 거리가 짧은 간선부터 돌아봐야 하므로 오름차순 정렬 필수!
}

int find(int x) {
	if (parent[x] == x) return x;
	int y = parent[x];
	parent[x] = find(y);
	return parent[x];
}

bool isUnion(int start, int end) {
	int p1 = find(start);
	int p2 = find(end);
	if (p1 == p2) return true;
	else {
		if (p1 > p2) {
			parent[p1] = p2;
			return false;
		}
		else {
			parent[p2] = p1;
			return false;
		}
	}
	
}

void setMST() {
	int cnt = 0;
	cost = 0;
	for (int i = 0; i < dist.size(); i++) {
		if (!isUnion(dist[i].start, dist[i].end)) {
			cost += dist[i].distance;
			if (++cnt >= N) {
				break;
			}
		}
	}
}

int main() {

	//freopen("swea1251_input.txt", "r", stdin);       // 입력파일
	int TC;
	scanf("%d ", &TC);

	for (int tc = 1; tc <= TC; tc++) {
		input();
		setDistance();
		setMST();

		printf("#%d %.0lf\n", tc, E*cost);			 // 결과값은 소숫점 첫째 자리에서 반올림하여 정수 형태 출력
	}


	return 0;
}

**** 주의할 점

• 자료형 주의: double, int, long long

 

 

 

 

 

<Reference>

-  https://swexpertacademy.com/main/main.do 

- https://blog.naver.com/PostView.nhn?blogId=1ilsang&logNo=221470205431&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView