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) { Tree *head; int i,rn,tn; int ix,mx1,mx2; head = GenerateTree(n); rn = head->child.size(); mx1 = GetMaxDepth(head,0)-1; ix = idx; for( i = mx2 = 0; i < rn; i++ ){ if( i == ix ) continue; tn = GetMaxDepth(head->child[i],0); if( mx2 < tn ) mx2 = tn; } idx = 0; ReleaseTree(head); 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; Tree *head; head = new Tree; for( i = mx = 0; i < n; i++ ){ if( mx < r[i] ){ mx = r[i]; tidx = i; } } head->x = x[tidx]; head->y = y[tidx]; head->r = r[tidx]; head->child.clear(); 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]; Recursion(head); } x.clear();y.clear();r.clear(); return head; } 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 문제를 풀고 있습니다만... 여러 예시를 만들어서 테스트해보고 다 해서 되는걸 확인했고 알고리즘 상으로도 딱히 문제는 없어보이는데 왜인지 굉장히 빠른 시간에 오답이 나서... 며칠간 고민해봤지만 사실 떠오르지가 않네요. 어떤 예시에서 문제가 발생했는지라도 하나만 알면 고칠 수 있을 것 같은데 도저히 못 고치겠네요...혹시 틀린 부분이 있을 것 같거나 아니면 틀린 예시라도 부탁드립니다.. 더이상은 이 문제에 시간을 쓰기도 힘드네요 ;; 풀것도 많은데.. 11년 전
2개의 댓글이 있습니다. JongMan 이거는 책에 보면 제가 설명해 둔 경우입니다만, 트리에서 가장 긴 경로는 두 잎 노드 사이에만 있는 것이 아닙니다. 다른 경우도 있으니 한번 생각해 보세요. 11년 전 link ggabu420 아.. 제가 다른 사람 얘기만 듣고 제 스스로 생각을 못했네요. 제일 처음 생각했었던 게 맞았었는데.. 감사합니다. 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
ggabu420
FORTRESS 문제를 풀고 있습니다만...
여러 예시를 만들어서 테스트해보고 다 해서 되는걸 확인했고
알고리즘 상으로도 딱히 문제는 없어보이는데
왜인지 굉장히 빠른 시간에 오답이 나서... 며칠간 고민해봤지만
사실 떠오르지가 않네요.
어떤 예시에서 문제가 발생했는지라도 하나만 알면
고칠 수 있을 것 같은데 도저히 못 고치겠네요...혹시
틀린 부분이 있을 것 같거나 아니면 틀린 예시라도 부탁드립니다..
더이상은 이 문제에 시간을 쓰기도 힘드네요 ;; 풀것도 많은데..
11년 전