[백준] 9370-미확인 도착지(C++)

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

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);
}