[알고스팟] FORTRESS - 요새 (C++, 트리)

문제

 

https://algospot.com/judge/problem/read/FORTRESS

algospot.com :: FORTRESS

 

 

풀이

 

종만북 난이도: 중

 

기하적인 문제 같아서 어려워 보이지만 성벽들은 서로 겹치거나 닿지 않기 때문에 모든 성벽들은 서로의 포함관계로

즉, 계층구조인 트리로 나타낼 수 있다.

 

성벽을 트리로 나타내면 문제의 답은 간단히 보인다.

바로 서로 가장 먼 두 노드 사이의 간선 수(경로)가 두 지점을 이동하기 위해 가장 많이 넘어야하는 성벽 수이다.

성벽을 가장 많이 넘어야하는 두 지점은 두 가지 경우가 존재한다. 

 

1. 서로 독립적으로 존재하는, 가장 많은 성벽으로 둘러 쌓인 두 지점

 성벽을 계층 구조로 나타냈을 때 서로 가장  잎과 잎 사이의 간선 수가 성벽의 수이다.

만약 잎이 아닌 노드를 임의의 지점으로 선택한다면, 그 노드의 하위 노드를 선택할 경우 더 긴 경로를 얻을 수 있기 때문에 오직 잎을 선택해야 최장 경로를 구할 수 있다.

 

2. 가장 깊은 성벽과 가장 외벽의 두 지점

 잎과 잎 사이의 간선 수보다 root노드(외벽)에서의 가장 깊은 잎으로의 경로가 큰 경우

 즉 트리의 높이가 답이 되는 경우이다.

예를 들면 아래와 같이 트리가 이루어지는 경우 두 개의 잎 노드보다 루트에서 잎까지의 경로가 더 크다.

 

 

 

이제 성벽의 트리를 구현해보자.

성벽들은 서로 겹치지지 않기 때문에 두 노드의 부모와 자식 관계가 성립하려면 부모 성벽의 반지름이 자식 노드의 반지름 보다 커야 한다.

 

성벽들을 반지름을 기준으로 내림차순 정렬 시

앞에 있는 성벽들(반지름이 더 큰 성벽들)이 뒤에 있는 성벽들을 포함할 수는 있지만 그 반대는 될 수 없다.

따라서 내림차순으로 정렬된 성벽을 순서대로 트리에 추가한다면 부모와 자식 관계가 결정된 노드 사이에 삽입되어 복잡한 연산을 거쳐야할 필요를 덜어준다.

 

이를 구현하기 위해 작성한 CastleNode 클래스에 정렬을 위한 '<' 연산자 오버로딩과 자식을 추가하는 AddChild 함수를 추가해주자.

 

 

class CastleNode{
  public:
  int x,y,r;
  vector<CastleNode*> children;
 
  CastleNode(int _x, int _y, int _r): x(_x), y(_y), r(_r){}
  
  void AddChild(CastleNode* b){
    CastleNode* a;
 
    for(int i=0; i<children.size() ; ++i){
      a = children[i];
      if(pow(a->r,2) > pow((a->x - b->x),2) + pow((a->y - b->y),2) + pow(b->r,2) ){
        children[i]->AddChild(b);
        return;
      }
      
    }
    children.push_back(b);
  }
 
  bool operator<(const CastleNode& cas) const{    // <연산자 오버로딩
    return (this->r) > (cas.r); 
  }
 
};
 

 

 

노드들은 정렬된 순서대로 추가되기 때문에 추가하는 노드는 특정 노드의 자식 노드가 될 수밖에 없다.

따라서 자신의 자식 노드들의 포인터를 저장하는 vector<CastleNode*> children를 순회하며 

CastleNode* b가 자신의 자식들에 포함될 수 있는지 확인한다.

 

성벽 간의 포함관계는 a 성벽의 지름이 더 크다고 가정할 때 

b 성벽과의 원점 사이의 거리 + b 성벽의 지름 < a 성벽의 지름

인 경우 a가 b를 포함한다. 

 

따라서 children들이 b를 포함하는지 확인하여

포함하는 경우, AddChild 함수를 재귀 호출을 해주고

모두 포함하지 않는 경우, a의 새로운 자식 노드로서 포함시켜준다.

 

 

 

이제 최대 몇 번 성벽을 넘어야 하는지 계산하자.

이는 트리의 높이를 구하는 것을 응용한다.

 

자신의 자식 노드의 서브 트리의 높이를 각각 구하여 반환시키고 만약 자식 노드가 두 개 이상이라면 잎과 잎 사이의 거리를 계산할 수 있다.

따라서 자식 노드 중에서 가장 높이가 큰 두 값을 더한 것이 자신이 루트로 존재하는 트리에서 가장 긴 잎과 잎 사이의 거리이다.

이를 전역 변수 longest와 비교하여 만약 해당 값이 더 크다면 longest를 업데이트 해주자.

최종적으로 앞에서 설명했듯이 루트에서 잎까지의 거리와 longest의 값을 비교해주어 더 큰 값이 정답이다.

 

 

int castle_num,longest;
vector<CastleNode> castles;
 
int TreeHeigth(CastleNode* cas){
  vector<int> heights;
  int max_height=0;
 
  if(cas->children.size() ==0)
    return 0;
  
  for(int i=0; i<cas->children.size() ; ++i){
    heights.push_back( TreeHeigth(cas->children[i]) + 1);
    max_height= max(max_height, heights.back());
  }
  
  if(cas->children.size()>1){
    sort(heights.begin(), heights.end());
    longest = max(longest, heights[heights.size() -1] + heights[heights.size() -2]);
  }
   
  return max_height;
}

 

 

코드