백준 14950 - 정복자(C++)

문제 링크입니다 https://www.acmicpc.net/problem/14950

14950번: 정복자

크루스칼 알고리즘을 사용하면 쉽게 풀리는 문제였습니다!

문제 조건

출력 예시

1번 도시는 정복하고 있기에 1번에서 최소 비용으로 갈 수 있는 곳을 먼저 정복한 뒤 Union+Find를 해주면 되는 문제였습니다!

 

문제 접근 방법

1. 백터에 시작점과 끝점, 비용을 저장한다.

2. 비용에 대해서 오름차순으로 정렬한다.

3. 1번 도시를 찾은 후, 먼저 연결해주고 시작한다.

4. Union+Find를 통해서 모든 도시를 정복하는데 필요한 최소 비용을 구한다.

 

 

문제 접근 방법 - 3번 + 4번

int Find(int x) {
	if (connect[x] == x) return x;
	else return connect[x] = Find(connect[x]);
}

void Union(int x, int y) {
	int xx = Find(x);
	int yy = Find(y);
	connect[xx] = yy;
}

void solve() {
	for (int i = 1; i <= N; i++) {
		connect[i] = i;
	}
	for (int i = 0; i < line.size(); i++) {
		if (line[i].x == 1) {
			connect[1] = line[i].y;
			answer += line[i].cost;
			conquer++;
			break;
		}
	}
	for (int i = 0; i < line.size(); i++) {
		int x = Find(line[i].x);
		int y = Find(line[i].y);
		if (x != y) {
			Union(x, y);
			answer += (line[i].cost + conquer * t);
			conquer++;
		}
	}
	cout << answer;
}

1번 도시는 이미 가지고 있기에 1번 도시에서 최소 비용으로 갈 수 있는 도시를 먼저 정복합니다.

그뒤에 비용에 대해서 오름차순한 vector를 통해서 Union+Find를 합니다. 한 도시를 정복할 때마다 비용을 올려주는 것을 잊으면 안됩니다!

 

자세한 것은 코드를 참고해주세요!

 

#define CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define MAX 100001
using namespace std;

int N, M, t;
int answer, conquer;
int connect[10001];
typedef struct li {
	int x;
	int y;
	int cost;
}li;
vector<li> line;

bool cmp(li a, li b) {
	if (a.cost < b.cost) return true;
	return false;
}

int Find(int x) {
	if (connect[x] == x) return x;
	else return connect[x] = Find(connect[x]);
}

void Union(int x, int y) {
	int xx = Find(x);
	int yy = Find(y);
	connect[xx] = yy;
}

void solve() {
	for (int i = 1; i <= N; i++) {
		connect[i] = i;
	}
	for (int i = 0; i < line.size(); i++) {
		if (line[i].x == 1) {
			connect[1] = line[i].y;
			answer += line[i].cost;
			conquer++;
			break;
		}
	}
	for (int i = 0; i < line.size(); i++) {
		int x = Find(line[i].x);
		int y = Find(line[i].y);
		if (x != y) {
			Union(x, y);
			answer += (line[i].cost + conquer * t);
			conquer++;
		}
	}
	cout << answer;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> t;
	for (int i = 0; i < M; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		line.push_back({ x,y,cost });
	}
	sort(line.begin(), line.end(), cmp);
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!