C++ 레퍼런스 (ECHMAScript syntax )구경과 백준 1774

https://cplusplus.com/reference/regex/

<regex> - C++ Reference

ECHMAScript syntax 

Regular operation does : pattern - matching - target sequence

But the regex syntax allows for special characters and expressions in the pattern:

 

Special pattern characters :

\d : digit

\D : not digit

\character 

 

Quantifiers 

*

+ 

?   : 0 or 1 

{int} : The preceding atom is matched exactly int times

{int,} :The preceding atom is matched int or more times.

{min,max} : The preceding atom is matched at least min times, but not more than max.

 

Groups

(subpattern)

(?:subpattern) 

 

Assertions : 

^ : start of line

$ : end of line

 

Seperator : | 

 

regex e(..)

regex_search(,..)

 

 

https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

문제를 읽고 나서 트리를 만드는 것이 목표임을 쉽게 이해했는데, 이 문제의 특이한 점은 트리가 미완성된 상태라는 것이었다. 트리(아니지만)가 몇 몇 노드 끼리는 연결되어 있지만 (노드 개수 - 1) 만큼의 간선은 없는 상태이다. 

그래서, 처음에는 이미 연결됨을 알고있는 노드들을 이용해서 프림 알고리즘을 사용하려고 생각했지만, 기존에 공부해서 친숙한 크루스칼 알고리즘으로 접근하였다.

주의할 점은 크루스칼 알고리즘을 구현할 때 간선의 길이는 보통 주어지는데 이 문제에서는 노드들의 좌표만 주어졌으므로 간선의 길이를 직접 구해야 한다.  그리고, 이미 연결된 노드들은 먼저 Union 한 뒤 시작해야 한다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int parent[1001]={-1,};
int height[1001]={0};

struct data {int x,y;};
vector<struct data> v;
double getDist(int a,int b){
    return sqrt(pow(v[a].x - v[b].x, 2) + pow(v[a].y - v[b].y, 2));
}

int Find(int u){
	if(parent[u]==-1) return u;
	return Find(parent[u]);
}
bool Union(int u,int v){
	u=Find(u);v=Find(v);
	if(u==v) return false;
	if(height[u]<height[v]) swap(u,v); 
		parent[v]=u;
	if(height[u]==height[v]) height[u]++;
	return true;
	
}
struct Edge{
	int u,v;
	double c;
	bool operator<(Edge rhs){
		return c<rhs.c;
	}
};
vector<Edge> edge;
int main() {
	int V,M;
	double ans=0; int cnt=0;
	cin>>V>>M;
	for(int i=1;i<=V;i++){
	    parent[i]=-1;
	    int x,y;cin>>x>>y;
	    v.push_back({x,y});
	}
	for(int i = 1; i<=V; i++){
		for(int j = 1; j <= V; j++){
		 if(i == j) continue;
		  double d = getDist(i-1,j-1);
		  edge.push_back({i,j,d});
		}
	}
	for(int i = 0; i < M; i++){
	    int x,y;cin>>x>>y;
	    Union(x,y);
	    cnt++;
	}
	sort(edge.begin(),edge.end());
	
	for(auto e:edge){
		int u=e.u,v=e.v; double c=e.c;
		if(Union(u,v)){
			ans+=c;
			cnt++;
		}
		if(cnt==V-1) break;
	}
	printf("%.2f",ans);
	return 0;
}