avoid 메모리 초과 런타임에러가 발생합니다

  • GilDong
    GilDong

    http://algospot.com/judge/problem/read/AVOID

    #include <stdio.h>
    #include <stdlib.h>
    #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
    int repeat=0;
    int spotAmount=0;
    int wayAmount=0;
    int destAmount=0;
    int ptFrom[4950]={};
    int ptTo[4950]={};
    int weight[4950]={};
    int destPt[4950]={};
    int temp=0;
    typedef struct stor
    {
        int sum;
        int step;
        int dir[4950];
    }stor;
    typedef struct link  //연결리스트 사용
    {
        stor memoPt;
        struct link* next;
    }link;
    
    link* startLink=NULL;
    link* lastLink=NULL;
    int storAmount=0;
    
    int partition(int list[],int left,int right)  //퀵정렬
    {
        int pivot,temp;
        int low,high;
        low=left;
        high=right+1;
        pivot=list[left];
        do{
            do
            {
                low+=1;
            }while(low<=right&&list[low]<pivot);
            do
            {
                high-=1;
            }while(high>=left&&list[high]>pivot);
            if(low<high)
            {
                SWAP(list[low],list[high],temp);
                SWAP(ptTo[low],ptTo[high],temp);
                SWAP(weight[low],weight[high],temp);
            }
        }while(low<high);
        SWAP(list[left],list[high],temp);
        SWAP(ptTo[left],ptTo[high],temp);
        SWAP(weight[left],weight[high],temp);
        return high;
    }
    void quick_sort(int list[],int left,int right)  //퀵정렬
    {
        if(left<right)
        {
            int q=partition(list,left,right);
            quick_sort(list,left,q-1);
            quick_sort(list,q+1,right);
        }
    }
    
    void func(int curNum,int loopNum,long long sum,stor memo) //재귀함수
    {
        if(curNum==ptTo[wayAmount-1])
        {
            memo.dir[memo.step++]=curNum;
            memo.sum=sum;
            link* newLink=(link*)malloc(sizeof(link));  //메모리 할당하는 부분!!
            newLink->memoPt=memo;
            newLink->next=NULL;
            if(storAmount==0)
            {
                startLink=newLink;
                lastLink=newLink;
            }
            else
            {
                lastLink->next=newLink;
                lastLink=newLink;
            }
            storAmount++;
            return;
        }
        for(int i=loopNum+1;i<wayAmount;i++)
        {
            if(curNum==ptFrom[i])
            {
                stor tempMemo=memo;
                tempMemo.dir[(tempMemo.step)++]=curNum;
                func(ptTo[i],i,sum+weight[i],tempMemo);
                continue;
            }
            else if(curNum<ptFrom[i])
                break;
        }
    }
    int main()
    {
        long long allWay=0;
        long long findNum=0;
        scanf("%d",&repeat);
        while(repeat--)
        {
            startLink=NULL;
            lastLink=NULL;
            storAmount=0;
            spotAmount=wayAmount=destAmount=0;
            scanf("%d %d %d",&spotAmount,&wayAmount,&destAmount);
            for(int i=0;i<wayAmount;i++)
            {
                scanf("%d %d %d",&ptFrom[i],&ptTo[i],&weight[i]);
                if(ptFrom[i]>ptTo[i])
                {
                    temp=ptTo[i];
                    ptTo[i]=ptFrom[i];
                    ptFrom[i]=temp;
                }
            }
            for(int i=0;i<destAmount;i++)
                scanf("%d",&destPt[i]);
    
            quick_sort(ptFrom,0,wayAmount-1);
    
            stor memo;
            memo.sum=0;
            memo.step=1;
            memo.dir[0]=1;
            for(int i=0;ptFrom[0]==ptFrom[i];i++)
                func(ptTo[i],i,weight[i],memo);
    
            link* findLink=startLink;
            if(storAmount>0)
            {
                int min=startLink->memoPt.sum;
                for(;findLink->next!=NULL;)
                {
                    if(min>findLink->memoPt.sum) min=findLink->memoPt.sum;
                    findLink=findLink->next;
                }
                for(int k=0;k<destAmount;k++)
                {
                    allWay=0;
                    findNum=0;
                    findLink=startLink;
                    link* nextLink=startLink;
                    for(;findLink->next!=NULL;)
                    {
                        findLink=nextLink;
                        if(min==findLink->memoPt.sum)
                        {
                            allWay++;
                            for(int j=0;j<findLink->memoPt.step;j++)
                            {
                                if(findLink->memoPt.dir[j]==destPt[k])
                                {
                                    findNum++;
                                    break;
                                }
                            }
                        }
                        nextLink=findLink->next;
                    }
                    if(allWay==0||findNum==0)
                    {
                        printf("0/1\n");
                        continue;
                    }
    
                    long long finalFindNum=findNum;
                    long long finalAllWay=allWay;
                    for(long long i=2;i<=finalFindNum;i++)
                    {
                        if(finalFindNum%i==0&&finalAllWay%i==0)
                        {
                            finalFindNum/=i;
                            finalAllWay/=i;
                        }
                    }
                    findNum=finalFindNum;
                    allWay=finalAllWay;
    
                    printf("%lld/%lld\n",findNum,allWay);
                }
                link* nextLink=startLink;
                for(findLink=startLink;findLink!=NULL;)
                {
                    nextLink=findLink->next;
                    free(findLink);  //메모리 제거하는부분
                    findLink=nextLink;
                }
            }
            else
            {
                printf("0/1\n");
                continue;
            }
    
    
        }
    
        return 0;
    }
    

    위에 주석달아놓은 부분에서 메모리 할당과 제거가 실행되고 누수는 발생하지 않게했습니다. 그런데 제출하면 메모리 초과했다고 오류를 보내주네요. 혹시 같은 경험하신분 조언부탁드려요


    10년 전
2개의 댓글이 있습니다.
  • Being
    Being

    메모리 할당 해제 문제를 떠나, 그냥 메모리 사용량이 지나치게 많은 것 같습니다. stor 구조체가 int를 대략 5000개 가졌으므로 20kb를 차지하는데, link 구조체가 이것을 하나씩 가지면서 리스트로 보관하므로 대략 100MB 근처까지 갈 것 같네요.


    10년 전 link
  • GilDong
    GilDong

    발코딩 ㅜㅜ


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