이것 저것 &

문제링크: https://www.acmicpc.net/problem/1774

MST문제 

접근방식

1. 모든 노드를 잇는 최소비용을 출력하는 것이기 때문에 MST문제임을 인식

2. 우선순위 큐를 사용한 프림알고리즘을 사용하기로 함

문제풀이 

1. 일반적인 프림알고리즘과 거의 동일한 구조

2. 조심해야할 점은 결과값이 소수형태이기 때문에 그 부분에 유의하면서 자료형을 선택해야한다. 

3. dis에 거리를 다 넣어놓고 탐색하는 구조

코드를 보면 더 이해가 빠를 듯

정답 코드

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

int n, m;
bool visited[1001] = { 0, };
int arr[1001][2] = { 0, };	
double dis[1001][1001] = { 0, };
double result = 0;
vector<pair<int, int>> vec;


void prim() {

	priority_queue <pair<double, int>> que; // 비용이랑 몇번째 좌표인지 표기
	for (int i = 2; i <= n; i++) { // 1과 연결된 값을 저장 
		que.push(make_pair(dis[1][i] * -1, i));
	}
	visited[1] = 1;

	while (!que.empty()) {
		double cost = que.top().first * -1;
		int cur = que.top().second;
		que.pop();

		if (visited[cur] == 0) {
			visited[cur] = 1;
			result += cost;

			for (int i = 1; i <= n; i++) {
				if (i != cur && visited[i] == 0) {
					que.push(make_pair(dis[cur][i] * -1, i));
				}
			}
		}


	}

}

int main() {

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> arr[i][0] >> arr[i][1];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dis[i][j] = sqrt(pow(abs(arr[i][0] - arr[j][0]), 2) + pow(abs(arr[i][1] - arr[j][1]), 2));
			dis[j][i] = dis[i][j];
		}
	//cout << dis[1][2] << endl;

	int t1, t2;
	for (int i = 0; i < m; i++) {
		cin >> t1 >> t2;
		dis[t1][t2] = 0, dis[t2][t1] = 0;
	}

	prim();
	printf("%.2f\n", result);
}

문제링크: https://www.acmicpc.net/problem/6497

최소 스패닝 트리를 만드는 문제입니다.

접근방식

1. 최소 스패닝 트리 알고리즘에 대해서 인지하고 있어야 한다.

2. MST는 크게 크루스칼 알고리즘, 프림 알고리즘이 존재한다. 

3. 나는 그 중에서 우선순위 큐를 사용한 프림알고리즘으로 문제를 해결했다. 

문제풀이 

1. 우선순위 큐에 1과 인접한 그래프 삽입 

2. visited로 방문 여부를 판단하며, 정점 - 1 개까지 반복 

 일반적인 bfs와 흡사한 방식

3. 전체 비용의 합 - 최소 경로의 합

아래는 정답코드입니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

vector <pair<int, int>> vec[200000];
bool visited[200000];
int m, n;
int result = 0;

void prim() {

	priority_queue <pair<int, int>> pq;
	visited[0] = true;
	for (int i = 0; i < vec[0].size(); i++) {
		pq.push(make_pair(-1 * vec[0][i].second, vec[0][i].first));
	}

	while (!pq.empty()) {
		int cost = pq.top().first * -1;
		int pos = pq.top().second;
		pq.pop();

		if (visited[pos] == false) {
			visited[pos] = true;
			result -= cost;
			
			for (int i = 0; i < vec[pos].size(); i++) {
				int ncost = vec[pos][i].second;
				int npos = vec[pos][i].first;
				if (visited[npos] == false)
					pq.push(make_pair(ncost*-1, npos));
			}

		}


	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	while (1) {
		cin >> m >> n;
		if (m == 0 && n == 0)
			break;

		for (int i = 0; i < m; i++)
			vec[i].clear();

		result = 0;
		int from, to, cost;
		for (int i = 0; i < n; i++) {
			cin >> from >> to >> cost;
			vec[from].push_back(make_pair(to, cost));
			vec[to].push_back(make_pair(from, cost));
			result += cost;
		}

		memset(visited, 0, sizeof(visited));
		
		prim();
		cout << result << endl;
	}

	
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1922

기본적인 최소스패닝트리(MST)문제

접근방식

1. 최소 스패닝 트리 알고리즘에 대해서 인지하고 있어야 한다.

2. MST는 크게 크루스칼 알고리즘, 프림 알고리즘이 존재한다. 

3. 나는 그 중에서 우선순위 큐를 사용한 프림알고리즘으로 문제를 해결했다. 

문제풀이 

1. 우선순위 큐에 1과 인접한 그래프 삽입 

2. visited로 방문 여부를 판단하며, 정점 - 1 개까지 반복 

 일반적인 bfs와 흡사한 방식

아래는 정답 코드입니다. 최소 스패닝 트리에 대해 알고 있는지 확인하는 문제였습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int INF = 2000000000;
int n, m;
vector <pair<int, int>> vec[1001];
vector <pair<int, int>> selected;
bool visited[1001] = { 0, };

int result = 0;
void prim() {

	priority_queue <pair<int, int>> pq;
	for (int i = 0; i < vec[1].size(); i++) {
		int to = vec[1][i].first;
		int co = vec[1][i].second;
		pq.push(make_pair(-1 * co, to));
	}

	visited[1] = 1;
	while (!pq.empty()) {
		int co = pq.top().first * -1;
		int to = pq.top().second;
		pq.pop();

		if (visited[to] == false) {

			visited[to] = true;
			result += co;

			for (int i = 0; i < vec[to].size(); i++) {
				int nto = vec[to][i].first;
				int nco = vec[to][i].second;

				if(visited[nto] == false)
					pq.push(make_pair(-1 * nco, nto));
			}
		}



	}

}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	cin >> m;

	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
	}

	prim();
	
	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1647

접근방식

1. 집들을 연결하는 최소값임으로  MST(최소 스패닝 트리) 문제임을 인지

문제풀이 

1. 일반적인 스패닝 트리를 구현

2. 두마을로 분리를 하는 것은 연결된 스패닝 트리 간선중에서 가장 값이 큰 것을 제거해줌으로 구현

3. 저는 우선순위를 사용한 prim 알고리즘으로 구현했습니다.

아래는 정답 코드

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

int n, m, result = 0;
int cut_val = 0;
vector <pair<int, int>> vec[100001];
bool visited[100001] = { 0, };

void prim() {
	priority_queue <pair<int, int>> pq;
	for (int i = 0; i < vec[1].size(); i++) {
		int cost = vec[1][i].second;
		int pos = vec[1][i].first;
		pq.push(make_pair(-1 * cost, pos));
	}
	visited[1] = 1;

	while (!pq.empty()) {

		int cost = pq.top().first * -1;
		int pos = pq.top().second;
		pq.pop();

		if (visited[pos] == false) {
			visited[pos] = true;
			result += cost;
			
			cut_val = max(cut_val,cost);
			for (int i = 0; i < vec[pos].size(); i++) {
				int ncost = vec[pos][i].second;
				int npos = vec[pos][i].first;
				if (visited[npos] == false) {
					pq.push(make_pair(-1 * ncost, npos));
				}
			}


		}

	}

}

int main() {
	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
	}

	prim();
	cout << result - cut_val << endl;


	return 0;
}