boj 9373: 복도뚫기

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

9373번: 복도 뚫기

MST를 이용한 심화 문제이다.

MST는 기본적으로 젤 가중치 작은 edge부터 더해나간다. 잘 생각해보면 위 그림에서 빨간선으로 연결된 것 중에서 검은색 갭중에 가장 가중치가 큰것(거리가 긴것)을 고르면 그게 답이다. 양단의 두 벽을 노드로 간주하고 모든 파란색 볼 노드와 연결을 하면, 두 벽의 parent가 동일해 질대까지만 MST를 사용을 했을때, 사용한 edge들중 max값이 지름은 원은, 어떤 다른 장애물이 있어도, 그 사이 gap을 지나갈 수 있을 것이다. 그 이유는 당연히 MST가 가장 짧은 edge들부터 더해나가기 때문이다. 여기서는 더하지는 않고, 벽의 parent가 같아졌을때의 edge값의 1/2값이 답이다.

 

여기서 가장 많이 틀렸던 부분이, 제곱 부분이다. double을 사용하여 나타내고자 한다면, (x1-x2)*(x1-x2)대신, pow(x1-x2,2)를 써야만 

"맞았습니다!" 가 뜬다.

 

#include<bits/stdc++.h>
using namespace std;

int tc,w,n,x,y,r,p[1010];

int Find(int x){
  if(x==p[x]) return x;
  return p[x] = Find(p[x]);
}

void Union(int x, int y){
  int x1=p[x], y1=p[y];
  if(x1<y1){
    p[y1]=x1;
    Find(y);
  }else{
    p[x1]=y1;
    Find(x);
  }
  return;
}

double dist(int x1,int y1,int x2,int y2){
  return sqrt(pow(x1-x2,2)+pow(y1-y2,2)+.0); // double return할때는 반드시 Pow 사용해야한다.
}

bool comp(pair<double,pair<int,int>>&a, pair<double,pair<int,int>>&b){
  return a.first < b.first; // double sort할때는 이렇게 써도 괜찮다.
}

int main(){

  cin>>tc;
  while(tc--){
    double ans = 0;
    int wall_right=1001, wall_left=0;
    cin>>w;
    cin>>n;
    vector<pair<int,pair<int,int>>> Circle (n+2);
    vector<pair<double,pair<int,int>>> edge;
    edge.push_back({w+.0,{wall_left,wall_right}});
    for(int i=0;i<=1001;i++) p[i]=i;
    for(int i=1;i<=n;i++){
      cin>>x>>y>>r;
      Circle[i].first=r;
      Circle[i].second.first=x;
      Circle[i].second.second=y;
    }
    for(int i=1;i<=n;i++){
      int rad=Circle[i].first,posx=Circle[i].second.first,posy=Circle[i].second.second;
      edge.push_back({max(posx-rad+.0,.0),{wall_left,i}});
      edge.push_back({max(w-posx-rad+.0,.0),{wall_right,i}});
    }
    for(int i=1;i<n;i++){
      for(int j=i+1;j<=n;j++){
        int rad1=Circle[i].first,posx1=Circle[i].second.first,posy1=Circle[i].second.second;
        int rad2=Circle[j].first,posx2=Circle[j].second.first,posy2=Circle[j].second.second;
        double d=dist(posx1,posy1,posx2,posy2);
        edge.push_back({max(d-rad1-rad2+.0,.0),{i,j}});
      }
    }
    sort(edge.begin(),edge.end(),comp);
    cout.precision(6);
    cout<<fixed;
    for(auto &e:edge){
      double cost=e.first;
      int from=e.second.first, to=e.second.second;
      if(Find(from) != Find(to)){
        Union(from,to);
        ans=cost;
      }
      if(Find(wall_left)==Find(wall_right)){
          cout<<ans/2+.0<<'\n';
          break;
      }
    }
  }



  return 0;
}