FORTRESS 자꾸 오답나오네요. 뭐가 잘못된걸까요...도와주세요~!

  • mook1993@naver.com
    mook1993@naver.com

    책에 있는 아이디어 참고해서 제 나름 대로 한다고 했는데 제출하면 자꾸 오답처리 되네요...
    제 소스코드에서 어떤게 문제점이 될 수 있는지 찾아주시면 감사하겠습니다~!!!

    문제 URL
    FORTRESS: 요새

    고려한 사항들

    • 트리의 높이와 leaf-leaf의 값 중 최댓값을 답으로...
    • 하나의 노드는 여러개의 자식을 가질 수 있음
    • 트리 생성시에 노드를 차례차례로 입력하여 알맞은 위치에 삽입되게 끔 함

    package FORTRESS;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.StringTokenizer;
    
    class circleInfo{
        int x, y, r;
    }
    class TreeNode{
        TreeNode parent=null;
        circleInfo data=new circleInfo();
        ArrayList<TreeNode> child=new ArrayList<TreeNode>();
    }
    public class Main {
        static int longest=0;
        public static void main(String[] args) throws IOException {
            // TODO Auto-generated method stub
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int TestCase=Integer.parseInt(br.readLine());
    
            for(int tc=0;tc<TestCase;tc++) {
                int N=Integer.parseInt(br.readLine());
    
                TreeNode[] nodeArr=new TreeNode[N];
    
                for(int i=0;i<N;i++) {
                    nodeArr[i]=new TreeNode();
                    StringTokenizer st=new StringTokenizer(br.readLine());
                    nodeArr[i].data.x=Integer.parseInt(st.nextToken());
                    nodeArr[i].data.y=Integer.parseInt(st.nextToken());
                    nodeArr[i].data.r=Integer.parseInt(st.nextToken());
                }
    
                TreeNode root=nodeArr[0];
                //성벽에 포함관계에 알맞게끔 노드를 트리에 삽입
                for(int i=1;i<nodeArr.length;i++)
                    addNode(root,nodeArr[i]);
    
                longest=longestLeaf2LeafDistance(root);
                LongestDistance(root);
                int result=Math.max(longest, treeHeight(root));
    
                System.out.println(result);
                longest=0;
            }
        }
    
        //root트리의 서브트리에서 leaf-루트-leaf의 최대 경로 반환
        static void LongestDistance(TreeNode root) {
            if(root.child.size()==0) return;
            for(int i=0;i<root.child.size();i++) {
                longest=Math.max(longest, longestLeaf2LeafDistance(root.child.get(i)));
                LongestDistance(root.child.get(i));
            }
        }
    
        //n을 root로 했을때 leaf-root-leaf간 최대거리
        static int longestLeaf2LeafDistance(TreeNode n) {
            int max1=0,max2=0;
            if(n.child.size()<2) return 0;
    
            for(int i=0;i<n.child.size();i++) {
                int treeH=treeHeight(n.child.get(i));
                if(max1<treeH) {
                    max2=max1;
                    max1=treeH;
                }else if(max1>=treeH && max2<treeH) {
                    max2=treeH;
                }
            }
            return max1+max2+2;
        }
    
        //트리의 높이반환 O(n)
        static int treeHeight(TreeNode n) {
            if(n.child.size()==0) return 0;
            int maxH=0;
            for(int i=0;i<n.child.size();i++) {
                int childH=treeHeight(n.child.get(i));
                if(maxH<childH)
                    maxH=childH;
            }
            return maxH+1;
        }
    
        //포함관계에 알맞게끔 트리에 노드를 추가
        static void addNode(TreeNode root, TreeNode elem) {
            int flagIsChild=isChild(root, elem);
    
            if(flagIsChild==1) {
            //root가 elem을 포함하는 경우, root의 자식과의 포함관계를 탐색
                for(int i=0;i<root.child.size();i++) {
                    int fc=isChild(root.child.get(i),elem);
                    if(fc==1) { //만약 root.child[i]가 elem을 포함한다면 child를 root로 해서 재귀호출
                        addNode(root.child.get(i),elem);
                        return;
                    }else if(fc==-1) {  //만약 elem이 root.child[i]를 포함한다면, 그 사이에 삽입
                        root.child.get(i).parent=elem;
                        elem.parent=root;
                        return;
                    }
                }
                root.child.add(elem);
            }else if(flagIsChild==-1) {
            //elem이 root를 포함, root와 root의 부모사이에 elem을 삽입
                elem.parent=root.parent;
                root.parent=elem;
            }else {
                // 포함관계가 아닌 경우, 형제로 만들어 줌
                root.parent.child.add(elem);
            }
        }
    
        //두 노드간 포함관계를 반환
        static int isChild(TreeNode root, TreeNode elem) {
            double rootRadius=root.data.r;
            double elemRadius=elem.data.r;
            double d=Math.sqrt(Math.pow(root.data.x-elem.data.x, 2)+Math.pow(root.data.y-elem.data.y, 2));
    
            if(rootRadius>elemRadius && d<rootRadius-elemRadius)//root가 elem을 포함하는 경우, 1반환
                return 1; 
            else if(rootRadius<elemRadius && d<elemRadius-rootRadius)//elem이 root를 포함, -1반환
                return -1;
    
            return 0;   //둘 관계가 서로 포함관계가 아니면 0반환
        }
    
    }
    
    }
    


    3달 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.