## FORTRESS 문제 질문 드립니다..

• ggabu420

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef struct _Tree
{
int x,y,r;
vector<struct _Tree *> child;
}Tree;

vector<int> x,y,r;
int rx,ry,rr,idx;

int fortress(int);
Tree *GenerateTree(int);
void ReleaseTree(Tree*);
int GetMaxDepth(Tree*,int);
int  Recursion(Tree*);
bool inCircle(int,int,int,int,int,int);

int main()
{
int i,j;
int c,n,t;

cin >> c;
for( i = 0; i < c; i++ ){
cin >> n;
for( j = 0; j < n; j++ ){
cin >> t;
x.push_back(t);
cin >> t;
y.push_back(t);
cin >> t;
r.push_back(t);
}
cout << fortress(n) << endl;
}
return 0;
}
int fortress(int n)
{
int i,rn,tn;
int ix,mx1,mx2;

ix = idx;
for( i = mx2 = 0; i < rn; i++ ){
if( i == ix ) continue;
if( mx2 < tn ) mx2 = tn;
}

idx = 0;
return mx1+mx2;
}
int GetMaxDepth(Tree *tr, int dep)
{
int i,n,ret;
int depth;

n = tr->child.size();
depth = 0;

for( i = 0; i < n; i++ ){
ret = GetMaxDepth(tr->child[i],dep+1);
if( depth < ret ){
depth = ret;
if( !dep ) idx = i;
}
}
return depth+1;
}
Tree *GenerateTree(int n)
{
int i,tidx,mx;

for( i = mx = 0; i < n; i++ ){
if( mx < r[i] ){
mx = r[i];
tidx = i;
}
}

x.erase(x.begin()+tidx);
y.erase(y.begin()+tidx);
r.erase(r.begin()+tidx);

for( i = 0; i < n-1; i++ ){
rx = x[i];
ry = y[i];
rr = r[i];
}

x.clear();y.clear();r.clear();
}
void ReleaseTree(Tree *tr)
{
int i,n;

n = tr->child.size();
for( i = 0; i < n; i++ )
ReleaseTree(tr->child[i]);

delete tr;
}
int Recursion(Tree *tr)
{
int i,n,ret;
Tree *t;

if( inCircle(rx,ry,rr,tr->x,tr->y,tr->r) ){
n = tr->child.size();
for( i = 0; i < n; i++ ){
ret = Recursion(tr->child[i]);
if( ret == 1 ) return 1;
else if( ret == 2 ){
t = new Tree;
t->x = rx;
t->y = ry;
t->r = rr;
t->child.push_back(tr->child[i]);
tr->child.erase(tr->child.begin()+i);
tr->child.push_back(t);
return 1;
}
}
t = new Tree;
t->x = rx;
t->y = ry;
t->r = rr;
t->child.clear();
tr->child.push_back(t);
return 1;
}
else if( inCircle(tr->x,tr->y,tr->r,rx,ry,rr) ) return 2;

return 0;
}
bool inCircle(int x1, int y1, int r1, int x2, int y2, int r2)
{
double t;

if( r1 >= r2 ) return false;
else{
t = sqrt( (double)(((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1))) );
if( (double)r2 > t ) return true;
}
return false;
}


FORTRESS 문제를 풀고 있습니다만...
여러 예시를 만들어서 테스트해보고 다 해서 되는걸 확인했고
알고리즘 상으로도 딱히 문제는 없어보이는데
왜인지 굉장히 빠른 시간에 오답이 나서... 며칠간 고민해봤지만
사실 떠오르지가 않네요.

어떤 예시에서 문제가 발생했는지라도 하나만 알면
고칠 수 있을 것 같은데 도저히 못 고치겠네요...혹시
틀린 부분이 있을 것 같거나 아니면 틀린 예시라도 부탁드립니다..
더이상은 이 문제에 시간을 쓰기도 힘드네요 ;; 풀것도 많은데..

7년 전
##### 2개의 댓글이 있습니다.

• JongMan

이거는 책에 보면 제가 설명해 둔 경우입니다만, 트리에서 가장 긴 경로는 두 잎 노드 사이에만 있는 것이 아닙니다. 다른 경우도 있으니 한번 생각해 보세요.

7년 전

• ggabu420

아.. 제가 다른 사람 얘기만 듣고 제 스스로 생각을 못했네요.
제일 처음 생각했었던 게 맞았었는데.. 감사합니다.

7년 전
• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.