[트리] [시도 x]FORTRESS 요새

1. 트리 생성

 

이 문제는 외벽안의 성벽들을 트리로 나타낸다음

각 잎에서 잎까지의 경로가 가장 긴 거리를 구하는 문제이다.

 

따라서 일단 주어진 성벽들의 정보를 가지고 

트리를 구성해야한다.

 

이 트리를 생성하는데

 

약 n*n*n 이 걸릴 것 같다.

 

1. 서로 비교하여 노드의 벡터에 포함되어있는것을 넣는다 -> 두개를 비교하니 n*(n-1)/2

2. 각 비교할때마다 부모노드에서 자식노드벡터를 제거해야한다 -> n(점점 작아진다 생각보다 빨리 실행될 것이다)

3. 넣은것들 또한 트리로 정리해야하므로 남은 것들을 재귀호출해야한다. -> n

 

2번은 총 n(n-1)/2 번 실행될것이고 , 1번 또한 n(n-1)/2 번 실행될것이니

대략 n^2만에 트리를 정리하여 서브 트리만 남겨놓는다.

서브트리를 재귀로 정리해야한다. -> n (점점 작아져 생각보다 빨리 실행될 것이다.)

따라서  O(n^3) 의 시간복잡도를 가질 것이다.

 

2. 트리의 높이

 

bfs로 각 잎들을 탐색하면서 잎간의 거리를 구할 수 있을 것이다.

 

같은 높이에 있을 시 거리가 줄어들기 때문에 단순 높이 정보만으로는 해결하기 때문에 

트리를 이용해 직관적으로 문제를 풀 수 있다.

 

3. 책의 풀이

 

isChild 와 getTree 함수는 트리를 생성하고

height와 solve는 잎-잎경로와 잎-루트 경로 길이중 최장길이를 리턴하는 함수이다.

 

height는 각 노드를 순회하며 그 노드에서 뻗어나가는 서브트리중 두개의 가장 큰 높이를 구하고 더하여 거리를 구한다.

(두개가 없을 시 높이)

 

isChild는 루트와 노드들을비교해가며 이것이 루트와 연결될 수 있는지 판단한다.

            루트와 연결되는것들은 루트 외에는 어떤것에도 포함되서는 안된다.

            즉 encloses(parent, i) && encloses(i, child) 가 되서는 안된다.

getTree는 각 노드를 순회하면서 root와 직접적으로 연결될 수 잇는지 확인하고 목록에 추가한다.

 

getTree는 총 n 번 실행되며, for문에서 n 번, ischild에서 n번의 비교를 하므로

트리를 생성하는 총 시간은 예측한대로 O(N^3)이다.

 

트리를 생성하는 시간은 미리 성벽의 크기를 정렬함으로써 O(n^2)으로 줄일 수 있다.

이는 트리를 잎에서부터 시작해 거꾸로 생성해 올라오는 것이다.

(크기가 자기보다 작은것에 포함될 수 없다.)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//longest path
 
struct TreeNode {
    vector<TreeNode*> children;
};
 
int longest;
 
int height(TreeNode* root)
{
    vector<int> heights;
    for(int i = 0 ; i < root->children.size(); i++)
        heights.push_back(height(root->children[i]));
 
    if(heights.empty()) return 0;
    sort(heights.begin(), heights.end());
 
    if(heights.size() >= 2)
        longest = max(longest, 2 + heights[heights.size()-1] + heights[heights.size() - 1]);
    return heights.back() + 1;
}
 
int solve(TreeNode* root)
{
    longest = 0;
    int h = height(root);
    return max(longest, h);
}
 
int n;
int n, y[100], x[100], r[100];
int sqr(int x)
{
    return x*x;
}
int sqrdist(int a, int b)
{
    return sqr(y[a] - y[b]) + sqr(x[a] - x[b]);
}
int encloses(int a, int b) 
{
    return (r[a] > r[b]) &&
        (sqrdist(a, b) < sqr(r[a] - r[b]));
}
bool isChild(int parent, int child)
{
    if(!encloses(parent, child)) return false;
    for(int i = 0; i < n; i++)
    {
        if(i != parent && i != child && encloses(parent, i) && encloses(i, child))
            return false;
    }
    return true;
}
TreeNode* getTree(int root) 
{
    TreeNode* ret = new TreeNode();
    for(int ch = 0; ch < n; ++ch)
    {
        if(isChild(root, ch))
            ret-> children.push_back(getTree(ch));
    }
    return ret;
}

FORTRESS