QUADTREE (쿼드 트리 뒤집기) 문제 문의

  • gloryof11
    gloryof11

    혼자힘으로(^^;) 트리를 이용해서 풀어보려고 했지만, 배열 크기 문제로 Runtime Error 가 발생하고 있습니다...

    혹시 QUADTREE 문제를 stdio.h 만 사용하여 해결하신 분이 계실까요?

    (문제 해결이 안되어 다른분 코드를 볼 수 없어 답답한 마음에 문의를 드리게 되었습니다;)

    컴파일 에러나는 코드 첨부하여드립니다;

    #include <stdio.h>
    //#include <time.h>
    
    int TC;
    char str[1000+1];
    unsigned long strlen;
    char tree[21][1099511627776]; // 컴파일 에러 나는 부분입니다.
    int depth;
    unsigned long loc[21];
    
    void makeTree(void)
    {
        for(int j=0;j<strlen;j++)
        {
            switch(str[j])
            {
                case 'x':
                    {
                        tree[depth][loc[depth]] = 'x';
                        depth += 1;
                        loc[depth] = loc[depth-1]*4;
                    }
                    break;
                case 'w':
                    {
                        tree[depth][loc[depth]] = 'w';
                        if((loc[depth]+1)%4 == 0) depth--;
                        loc[depth] += 1;
                    }
                    break;
                case 'b':
                    {
                        tree[depth][loc[depth]] = 'b';
                        if((loc[depth]+1)%4 == 0) depth--;
                        loc[depth] += 1;
                    }
                    break;
            }
        }
    }
    
    void searchTree(void)
    {
        // only 1 node
        if(tree[0][0] != 'x') {
            printf("%c",tree[0][0]);
            return;
        }
    
        printf("x");
        depth = 1;
        loc[depth] = 2;
        for(int i=0;i<strlen-1;i++) // because of first 'x', condition is "i<strlen-1" 
        {
            switch(tree[depth][loc[depth]])
            {
                case 'x':
                    {
                        printf("x");
                        depth += 1;
                        loc[depth] = loc[depth-1]*4+2;
                    }
                    break;
                case 'w':
                    {
                        printf("w");
                        if((loc[depth]+3)%4 == 0) depth--;
                        loc[depth] += 1;
                        if(loc[depth]%4 == 0) loc[depth] -= 4;
                    }
                    break;
                case 'b':
                    {
                        printf("b");
                        if((loc[depth]+3)%4 == 0) depth--;
                        loc[depth] += 1;
                        if(loc[depth]%4 == 0) loc[depth] -= 4;
                    }
                    break;
            }
        }
    }
    
    int main(void)
    {
        //clock_t st = clock();
        freopen("input.txt", "r", stdin);
        //setbuf(stdout, NULL);
    
        scanf("%d",&TC);
        for(int i=0;i<TC;i++)
        {
            // init
            for(int j=0;j<1001;j++)
                str[j] = 0;
            strlen = 0;
            for(int j=0;j<11;j++)
                for(int k=0;k<1048576;k++)
                    tree[j][k] = 0;
            for(int j=0;j<11;j++)
                loc[j] = 0;
            depth = 0;
    
            // input str
            scanf("%s",&str);
            for(char* ptr = str;*ptr!=0;ptr++)
                strlen++;
    
            makeTree();
    
            // init
            for(int j=0;j<11;j++)
                loc[j] = 0;
            depth = 0;
    
            searchTree();   // DFS by 34,12 order
            printf("\n");
        }
    
        //printf("time : %d\n",clock()-st);
    
        return 0;
    }
    


    9년 전
3개의 댓글이 있습니다.
  • JongMan
    JongMan

    선언하신 배열의 크기가 대략 21테라바이트인데요.... 컴파일이 될 수 없겠죠. 이 문제는 압축을 배열에 푼 다음 다시 압축하는 방법으로는 푸실 수 없습니다.


    9년 전 link
  • gloryof11
    gloryof11

    사실 압축을 푼건 아니고요; 입력 문자열을 트리로 만든 다음, 자식방문 순서를 3,4,1,2 로 깊이우선탐색 하고자 했었습니다; stdio.h 만 사용하는 제약을 가지고 문제를 해결하려 했었는데, 링크드리스트로 트리를 만들어 봐야 겠네요. 답변 감사드립니다!


    9년 전 link
  • yukariko
    yukariko

    저도 최근에 이 문제를 풀어봤습니다만
    stdio.h에 있는 함수만으로도 풀이가 가능했습니다.
    언어는 cpp 이었지만 c로 바꿔도 전혀 문제될것이 없는 코드였기 때문에 답변해봅니다.


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