[ALGOSPOT] 요새 (FORTRESS)

algospot.com/judge/problem/read/FORTRESS

algospot.com :: FORTRESS

<문제>

중세의 성과 요새들은 보안을 튼튼히 하면서도 더 넓은 영역을 보호하기 위해 여러 개의 성벽을 갖고 있었다고 하지요. 전세계에서 가장 편집증이 심한 영주가 지은 스트로고(Strawgoh) 요새는 이의 극치를 보여줍니다. 이 요새는 그림과 같이 커다란 원형 외벽 내에 여러 개의 원형 성벽이 겹겹이 지어진 형태로 구성되어 있는데, 어떤 성벽에도 문이 없어서 성벽을 지나가려면 사다리를 타고 성벽을 오르내려야 합니다. 요새 내에서도 한 곳에서 다른 곳으로 이동하는 데 시간이 너무 오래 걸린다는 원성이 자자해지자, 영주는 요새 내에서 왕래가 불편한 곳들을 연결하는 터널을 만들기로 했습니다. 계획을 세우기 위해 요새 내에서 서로 왕래하기 위해 가장 성벽을 많이 넘어야 하는 두 지점을 찾으려고 합니다. 예를 들어 위 그림의 경우, 별표로 표시된 두 지점 간을 이동하기 위해서는 다섯 번이나 성벽을 넘어야 하지요.

성벽들의 정보가 주어질 때 가장 성벽을 많이 넘어야 하는 두 지점 간을 이동하기 위해 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하세요.

 

<입력>

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 성벽의 수 N (1 <= N <= 100) 이 주어집니다. 그 후 N 줄에는 각 3개의 정수로 각 성벽의 위치와 크기에 대한 정보 xi , yi , ri 가 주어집니다. (0 <= xi, yi <= 1000,1 <= ri <= 1000,0 <= i<N) 이 때 i 번 성벽은 (xi, yi) 를 중심으로 하는 반지름 ri 인 원형으로 설치되어 있습니다. 편의상 모든 성벽의 두께는 0이라고 가정하며, 입력에 주어지는 성벽들은 서로 겹치거나 닿지 않습니다. 입력에 주어지는 첫 번째 성벽은 외벽이며, 외벽은 입력에 주어지는 모든 다른 성벽을 포함합니다.

 

<출력>

각 테스트 케이스마다 한 줄에 두 지점 간 이동을 위해 최대 몇 번이나 성벽을 넘어야 하는지를 출력하세요.

 

<예제 입력>

2

3

5 5 15

5 5 10

5 5 5

8

21 15 20

15 15 10

13 12 5

12 12 3

19 19 2

30 24 5

32 10 7

32 9 4

 

<예제 출력>

2

5

 

<아이디어>

입력에 주어지는 성벽들은 서로 겹치거나 닿지 않기 때문에, 이 문제에서 고려해야할 경우의 수는 두가지 이다.

두 원의 중심 사이의 거리가 큰 원의 반지름 보다 큰 경우

두 원의 중심 사이의 거리가 큰 원의 반지름보다 작은 경우

큰 원을 부모 노드, 작은 원을 자식 노드로 두면 트리 구조를 만들 수 있다.

 

넘어가야할 최대 성벽의 수는 가장 멀리있는 두 노드간의 거리를 구하면 된다.

가장 멀리있는 두 노드간의 거리를 구하는 방법은 다음과 같다.

1. 트리에서 임의의 정점 v를 잡는다.

2. v에서 가장 멀리 있는 정점 v1을 구한다.

3. v1에서 가장 멀리 있는 정점 v2를 구한다.

 

이때,  v1과 v2의 거리가 트리에서 가장 멀리있는 두 노드간의 거리이다. (트리의 지름)

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
struct wall
{
    int y;
    int x;
    int r;
 
    wall()
    {
        y = 0;
        x = 0;
        r = 0;        
    }
    wall(int y, int x, int r)
    {
        this->y = y;
        this->x = x;
        this->r = r;
    }
};
 
bool compare(wall &A, wall &B)
{
    return A.r > B.r;
}
 
double get_sqdist(wall &a, wall &b)
{
    return (a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x);
}
 
void init(int node, int pos, vector<wall>& wallv, vector<vector<int>>& tree,
            vector<bool>& check
            )
{
    bool flag = false;
    check[node] = true;
    for(size_t i=0;i<tree[node].size();i++)
    {
        int tmp = tree[node][i];
        if(check[tmp]) continue;
        int mxr = max(wallv[tmp].r, wallv[pos].r);
        if(get_sqdist(wallv[tmp], wallv[pos]) < mxr*mxr)
        {
            flag = true;
            init(tmp, pos, wallv, tree, check);
            break;
        }
    }
    if(!flag)
    {
        tree[node].push_back(pos);
        tree[pos].push_back(node);
    }
}
 
int depth, fnode;
 
void dfs(int pos, int node, vector<vector<int>>& tree, vector<bool>& check)
{
    check[node] = true;
    if(pos > depth)
    {
        depth = pos;
        fnode = node;
    }
    for(size_t i=0;i<tree[node].size();i++)
    {
        int tmp = tree[node][i];
        if(check[tmp]) continue;
        dfs(pos+1, tmp, tree, check);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        vector<wall> wallv(n, wall());
        int tmpy, tmpx, tmpr;
        for(int i=0;i<n;i++)
        {
            cin>>tmpx>>tmpy>>tmpr;
            wallv[i] = wall(tmpy, tmpx, tmpr);
        }
        sort(wallv.begin(), wallv.end(), compare);
        vector<vector<int>> tree(n, vector<int>());
        vector<bool> check(n, false);
        
        for(int i=1;i<n;i++)
        {
            fill(check.begin(), check.end(), false);
            init(0, i, wallv, tree, check);
        }
 
        depth = 0;
        fnode = 0;
        fill(check.begin(), check.end(), false);
        dfs(0, 0, tree, check);
        fill(check.begin(), check.end(), false);
        dfs(0, fnode, tree, check);
        cout<<depth<<endl;
    }
    return 0;
}