•
문제
황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.
하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다.
우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 이루어 진다. 하지만 우주신들과 교감하는 것은 힘든 일이기 때문에 황선자씨는 이런 통로들이 긴 것을 좋아하지 않는다. 왜냐하면 통로들이 길 수록 더 힘이 들기 때문이다.
또한 우리들은 3차원 좌표계로 나타낼 수 있는 세상에 살고 있지만 우주신들과 황선자씨는 2차원 좌표계로 나타낼 수 있는 세상에 살고 있다. 통로들의 길이는 2차원 좌표계상의 거리와 같다.
이미 황선자씨와 연결된, 혹은 우주신들과 연결된 통로들이 존재한다. 우리는 황선자 씨를 도와 아직 연결이 되지 않은 우주신들을 연결해 드려야 한다. 새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자.
풀이
모든 노드를 연결하면서, 노드를 연결하는 길이의 합이 최소가 되게 해야 한다 → MST!!
•
기본 알고리즘
1. 이미 연결되어 있는 통로를 MST에 추가한다.
2. MST를 구한다.
C++
복사
•
Union Find 함수
•
Path Compression을 통해 시간을 단축한다.
•
union-by-rank 기법은 실제 시간단축에 그렇게 큰 영향을 미치지 못한다.
int Find(int a) {
if (parent[a] == a) return a;
return parent[a] = Find(parent[a]); //Path Compression -> find하면서 만나는 모든 값의 부모를 root로 만듬
}
void Union(int a, int b) {
int x = Find(a);
int y = Find(b);
if (x == y) return;
if (x < y) parent[y] = x;
else parent[x] = y;
}
C++
복사
•
calc_dist 함수
•
노드 A, B가 주어졌을 때 A,B 사이의 거리를 구하는 함수
double calc_dist(int x, int y) { // 노드 번호 주면 두 노드 사이의 거리 출력
double x_dist = abs(god[x].first - god[y].first);
double y_dist = abs(god[x].second - god[y].second);
double dist = sqrt((x_dist * x_dist) + (y_dist * y_dist));
return dist;
}
C++
복사
•
Main 동작
•
입력을 받으면서 노드의 좌표값을 저장한다.
•
통로를 입력받을 때는 해당 통로를 MST에 추가한다.
•
Kruscal 알고리즘을 통해 MST를 구하며 가중치를 더해준다.
int main() {
fastio;
int N, M, X, Y;
int cnt = 0; // 시간단축 위해 N-1개의 엣지를 고르는 순간 바로 탈출하기 위한 변수
double result = 0;
cin >> N >> M;
for(int i = 1; i <= N; i++){
cin >> X >> Y; //좌표
god[i] = { X,Y };
parent[i] = i; // Union find 초기화
}
for (int i = 0; i < M; i++) {
cin >> X >> Y; //통로
Union(X, Y); //기존에 통로 주어졌으면 그건 무조건 포함시켜야 함
cnt++; //기존에 주어진 통로는 결과값에 포함 안하므로 cnt만 증가
}
// 모든 경로 만들어주기 어차피 양방향이니까 i < j 조건으로 시간단축
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
double dist = calc_dist(i, j);
path.push_back({ dist, i, j });
}
}
sort(path.begin(), path.end());
for (int i = 0; i < path.size(); i++) {
auto [dist, x, y] = path[i];
//x,y 노드가 이미 같은 집합 -> 지금 엣지 추가하면 싸이클 생김 -> MST X
if (Find(x) == Find(y)) continue;
Union(x, y);
cnt++;
result += dist;
if (cnt == N - 1) break; //빨리끝내기
}
cout.precision(2);
cout<< fixed << result;
return 0;
}
C++
복사
중요
소수를 활용할 때 자리수를 설정하는 방법
•
단순히 cout.precision()만 사용하는 경우에는 정수자리를 포함한 전체 숫자의 자리수를 결정한다.
•
따라서 소수점 이하 범위를 대상으로 지정하고 싶을 경우 cout<<fixed; 를 사용해야 한다.
cout.precision(2);
cout<< fixed << result;
return 0;
C++
복사
tuple
•
C++ 17 이상에서는 tuple의 원소를 가져올 때 get<0>tuple 없이 auto []를 통해 편하게 가져올 수 있다.
•
vector<tuple>의 경우에 algorithm 헤더의 sort 함수를 사용 가능하지만, greater<int>를 사용할 수없다. 내림차순으로 정렬하고 싶은 경우에는 cmp 함수를 만들어주어야 한다.
auto [dist, x, y] = path[i];
C++
복사
bool cmp(tuple<float, int, int> a, tuple<float, int, int> b) {
auto [x1, y1, z1] = a;
auto [x2, y2, z2] = b;
return x1 > x2;
}
C++
복사
