[BOJ] 4386 - 별자리 만들기
https://www.acmicpc.net/problem/4386
문제
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
입력
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
출력
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
예제 입출력
- 예제 입력 1
3
1.0 1.0
2.0 2.0
2.0 4.0
- 예제 출력 1
3.41
Solution
3
1.0 1.0
2.0 2.0
2.0 4.0
3.41
두 가지 방법을 사용할 수 있다.
1. Kruskal Algorithm
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 101
using namespace std;
vector<pair<double, double>> pointData;
vector<pair<double, pair<double, double>>> edge;
int Parent[MAX];
int getParent(int num){
if(num == Parent[num]) return num;
return Parent[num] = getParent(Parent[num]);
}
void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a != b) Parent[a] = b;
}
bool findParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a == b) return true;
else return false;
}
double kruskal(){
double result = 0;
sort(edge.begin(), edge.end());
for(int i = 0; i < edge.size(); i++){
double cost = edge[i].first;
int a = edge[i].second.first;
int b = edge[i].second.second;
if(!findParent(a, b)){
unionParent(a, b);
result += cost;
}
}
return result;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
for(int i = 0; i < MAX; i++) Parent[i] = i;
int N; cin >> N;
for(int i = 1; i <= N; i++){
double a, b;
cin >> a >> b;
pointData.push_back({a, b});
}
for(int i = 0; i < N; i++){
double x = pointData[i].first;
double y = pointData[i].second;
for(int j = i + 1; j < N; j++){
double xx = pointData[j].first;
double yy = pointData[j].second;
double dx = pow((x - xx),2);
double dy = pow((y - yy), 2);
double dist = sqrt(dx + dy);
edge.push_back({dist, {i, j}});
}
}
double answer = kruskal();
cout << answer << '\n';
}
코드가 겁나 길다. 크루스칼 알고리즘을 쓸 수 있도록 데이터들을 처리해주는 데 시간이 필요하다.
이 문제를 건드릴 정도면 크루스칼 알고리즘 정도는 이해하고 있을 가능성이 높다. 그래도 혹시 모르니 간략하게 설명하면 다음과 같다.
가능한 모든 경로들을 비용 순으로 오름차순 정렬한 후 Union Find 알고리즘을 통해 MST(Minimum Spanning Tree) 를 만들어 준다.
좌표들은 모두 입력받았다. 중요한 건, 이 좌표들을 경로들로 만들어야 한다는 것.
우선 입력받은 데이터들에 대해 모든 경로를 구해야 한다.
어차피 데이터가 많아봐야 100개다. 라고 한들 뭐 어쩌겠는가?
vector<pair<double, double>> pointData;
vector<pair<double, pair<double, double>>> edge;
int Parent[MAX];
int getParent(int num){
if(num == Parent[num]) return num;
return Parent[num] = getParent(Parent[num]);
}
void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a != b) Parent[a] = b;
}
bool findParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a == b) return true;
else return false;
}
pointData
는 좌표들의 데이터, edge
는 경로들의 데이터다. 크루스칼 알고리즘이니까 Union Find에 필요한 함수들과 각 노드들 Parent
배열이 필요하겠지.
for(int i = 0; i < MAX; i++) Parent[i] = i;
int N; cin >> N;
for(int i = 1; i <= N; i++){
double a, b;
cin >> a >> b;
pointData.push_back({a, b});
}
사전 작업을 해 준다. 모든 노드들(좌표들)의 Parent값을 본인으로 셋업해주고 모든 좌표값을 입력받는다.
for(int i = 0; i < N; i++){
double x = pointData[i].first;
double y = pointData[i].second;
for(int j = i + 1; j < N; j++){
double xx = pointData[j].first;
double yy = pointData[j].second;
double dx = pow((x - xx),2);
double dy = pow((y - yy), 2);
double dist = sqrt(dx + dy);
edge.push_back({dist, {i, j}});
}
}
double answer = kruskal();
cout << answer << '\n';
그 후 모든 좌표 데이터에 대해 경로를 구해준다. 두 점간의 거리 구하는 공식에 대해 설명 하지는 않겠다.
edge 데이터는 총 두개의 pair로 이루어진 가변배열(vector)이다. 비용, 노드 번호를 저장하기 위해서.
double kruskal(){
double result = 0;
sort(edge.begin(), edge.end());
for(int i = 0; i < edge.size(); i++){
double cost = edge[i].first;
int a = edge[i].second.first;
int b = edge[i].second.second;
if(!findParent(a, b)){
unionParent(a, b);
result += cost;
}
}
return result;
}
크루스칼 알고리즘은 뭐 크게 어렵지 않다. 우선 edge를 정렬한다. cost가 가변배열 노드에서 데이터 우선순위가 높기 때문에 cost 기준으로 정렬이 된다.
그 후 하나 하나 서치하면서 해당 경로, 시작 노드, 끝 노드를 가져와서 unionfind 알고리즘을 시행한다. unionParent 함수가 시행된다면 해당 cost를 사용했다는 의미이므로 result에 추가한다. 모든 탐색이 끝나면 return 한다.
2. Prim Algorithm
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 101
using namespace std;
vector<pair<double, double>> pointData;
vector<pair<int, double>> edge[MAX];
bool visited[MAX];
double prim(){
double result = 0;
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> PQ;
PQ.push({0, 0});
while(!PQ.empty()){
int next = PQ.top().second;
double minCost = PQ.top().first;
PQ.pop();
if(!visited[next]){
visited[next] = true;
result += minCost;
for(auto X : edge[next]){
if(!visited[X.first]) PQ.push({X.second, X.first});
}
}
}
return result;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for(int i = 0; i < N; i++){
double a, b;
cin >> a >> b;
pointData.push_back({a, b});
}
for(int i = 0; i < N; i++){
double x = pointData[i].first;
double y = pointData[i].second;
for(int j = i + 1; j < N; j++){
double xx = pointData[j].first;
double yy = pointData[j].second;
double dx = pow((x - xx),2);
double dy = pow((y - yy), 2);
double dist = sqrt(dx + dy);
edge[i].push_back({j, dist});
edge[j].push_back({i, dist});
}
}
double answer = prim();
cout << answer << '\n';
}
데이터 입력받는 건 같다. 하지만 문제를 잘 보면 알겠지만 단방향 그래프가 아니다.
프림 알고리즘 또한 아마 다들 알고있기는 하겠지만 간단히 설명하면 다음과 같다.
우선순위 큐를 활용하여 기준점이 되는 노드부터 탐색을 시작한다. 우선 순위 큐 내에 방문 한 노드에 대한 데이터가 있다면 빼버리고 남아있는 데이터 중 TOP에 존재하는 노드에 대한 경로 정보를 통해 해당 노드를 통해 갈 수 있는 노드들에 대한 데이터를 우선순위 큐에 갱신하고 해당 노드는 방문 처리 한다.
for(int i = 0; i < N; i++){
double x = pointData[i].first;
double y = pointData[i].second;
for(int j = i + 1; j < N; j++){
double xx = pointData[j].first;
double yy = pointData[j].second;
double dx = pow((x - xx),2);
double dy = pow((y - yy), 2);
double dist = sqrt(dx + dy);
edge[i].push_back({j, dist});
edge[j].push_back({i, dist});
}
}
단방향 그래프가 아니기때문에 입력받는 과정에서 약간의 차이가 있다. i
와 j
두 가지 노드에 대해 경로 데이터를 갱신해준다. i
에서j
로 가는, 그리고 j
에서 i
로 가는.
vector<pair<double, double>> pointData;
vector<pair<int, double>> edge[MAX];
bool visited[MAX];
그래서 edge 데이터도 다르다. Kruskal Algorithm
을 사용할 때는 해당 경로 자체를 가변행렬에 집어넣었다면, Prim Algorithm
은 마치 Adjacency Matrix
처럼 특정 노드와 연결 된 경로들의 데이터가 저장 된다. 각 노드별 방문을 확인하는 visited boolean 배열 또한 필요하다.
double prim(){
double result = 0;
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> PQ;
PQ.push({0, 0});
while(!PQ.empty()){
int next = PQ.top().second;
double minCost = PQ.top().first;
PQ.pop();
if(!visited[next]){
visited[next] = true;
result += minCost;
for(auto X : edge[next]){
if(!visited[X.first]) PQ.push({X.second, X.first});
}
}
}
return result;
}
본격적으로 Prim Algorithm
코드를 살펴보자. 제일 처음에는 0번 노드, 비용은 없음부터 시작한다.
while 문을 통해 구현한다. TOP에 있는 데이터를 기반으로 다음에 탐색 할 데이터를 갱신하고 해당 경로를 방문한 후, 해당 노드 기준으로 탐색 가능한 모든 경로를 PQ에 갱신한다.
마치 BFS와 흡사하다. Prim Algorithm
은 이런 양방향 그래프인 상황에서 사용 할 수 있다. Kruskal Algorithm
은 전체 경로를 크게 위에서 보면서 맞추는 느낌이라면 Prim Algorithm
은 실제로 탐색을 시켜보는 방식이다.
Outro
두 알고리즘은 각자 특징에 맞게 써야한다.
Kruskal Algorithm
- 간선 위주의 알고리즘
- 정렬하는 데 시간이 걸릴 수 있다.
- 간선의 갯수가 작을 때 유리하다.
Prim Algorithm
- 정점 위주의 알고리즘
- 최소 거리의 정점을 찾는 데 우선순위 큐에 의존한다.
- 간선의 갯수가 많을 때 유리하다.
Author And Source
이 문제에 관하여([BOJ] 4386 - 별자리 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sierra9707/BOJ-4386-별자리-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)