[9373번] 복도 뚫기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 스패닝 트리(MST) ::  http://www.crocus.co.kr/733

이 문제에 대한 접근은 다음과 같다.

우선 최소 스패닝 트리 개념으로 접근할 것이다.

1. 최소 스패닝 트리로 접근하기 위해 우선 센서와 복도를 생각해본다.

복도 좌, 우측 그리고 센서의 중심점을 각 정점으로 생각한다.

2. 이때 복도 좌측 x좌표는 0으로, 복도 우측 x좌표는 w로 생각하여 x좌표에 대해 정점들을 정렬한다.

이렇게 하는 이유는 최소 스패닝 트리에서 union을 쉽게 하기 위함이다.(큰 x좌표에서 작은 x좌표로 union한다는 개념으로)

3. 이때 인덱스 개념으로는 복도 좌측을 0번 인덱스, 복도 우측을 n + 1번 인덱스 그리고 센서를(센서의 반경을 하나의 부분 집합으로)

1~n번 인덱스로 생각한다.

4. 그렇게되면 n 범위가 최대 1000이기에 벽과 센서를 포함하여 모든 인덱스간의 간선을 구할 수 있다.

5. 그리고 그 간선들을 정렬하여 이제 최소 스패닝 트리 개념으로 접근한다.

6. 결국 크루스칼 알고리즘을 이용하여 해결하고, 두 벽이 연결되는 순간(find(0) == find(n+1)) 이 알고리즘은 종료된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
typedef struct _INFO_
{
    int x;
    int y;
    int r;
    int idx;
}INFO;
 
// 크루스칼 알고리즘에 이용할 struct
typedef struct _KS_
{
    int from;
    int to;
    double val;
}KS;
 
INFO info[1002];
int parent[1002];
bool chk;
 
bool comp(const INFO &a, const INFO &b)
{
    return a.x < b.x;
}
bool compVC(const KS &a, const KS &b)
{
    return a.val < b.val;
}
 
double getLength(int x1, int x2, int y1, int y2)
{
    return sqrt((ll)(x1 - x2)*(x1 - x2) + (ll)(y1 - y2)*(y1 - y2));
}
 
int find(int u)
{
    if (u == parent[u])
        return u;
 
    return parent[u] = find(parent[u]);
}
 
void merge(int u, int v)
{
    chk = false;
    u = find(u);
    v = find(v);
 
    if (u == v)
        return;
 
    parent[u] = v;
    chk = true;
}
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    while(tCase--)
    {
        int w, n;
        scanf("%d %d", &w, &n);
        
        // 초기화
        memset(info, 0, sizeof(info));
        vector<KS> vc;
        for (int i = 0; i <= n + 1; i++)
            parent[i] = i;
 
        info[0].x = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d %d %d", &info[i].x, &info[i].y, &info[i].r);
        info[n + 1].x = w;
 
        // 왼쪽 벽, 오른쪽 벽을 제외하고 정렬
        sort(info + 1, info + n + 1, comp);
 
        // 왼쪽 벽의 idx = 0
        info[0].idx = 0;
 
        // 그 외의 정점들은 x를 오름차순 기준으로 idx 정렬
        for (int i = 1; i <= n; i++)
            info[i].idx = i;
 
        // 오른쪽 벽의 idx = n + 1
        info[n + 1].idx = n + 1;
 
        // 벽사이 거리를 먼저 push
        vc.push_back(KS{ info[n + 1].idx, info[0].idx, (double)w });
        
        for (int i = 1; i <= n; i++)
        {
            int x = info[i].x;
            int r = info[i].r;
 
            double len = max(0, x - r);
 
            vc.push_back(KS{ info[i].idx, info[0].idx, len });
 
            len = max(0, w - x - r);
            vc.push_back(KS{ info[n + 1].idx, info[i].idx, len });
        }
 
        // 정점 사이 길이들
        for(int j = 1; j < n; j ++)
            for (int k = j + 1; k <= n; k++)
            {
                int x1 = info[j].x;
                int y1 = info[j].y;
                int x2 = info[k].x;
                int y2 = info[k].y;
 
                double len = getLength(x1, x2, y1, y2);
 
                vc.push_back(KS{ info[k].idx, info[j].idx, max((double)0.0, len - (double)info[j].r - (double)info[k].r)});
            }
 
        sort(vc.begin(), vc.end(), compVC);
 
        for(int i = 0; i < vc.size(); i ++)
        {
            merge(vc[i].from, vc[i].to);
 
            if (chk == true)
            {
                if (find(0) == find(n + 1))
                {
                    if (vc[i].val == 0)
                        printf("0\n");
                    else
                        printf("%.6lf\n", vc[i].val / 2);
                    break;
                }
            }
        }
 
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>