RESTORE 문제 좀 도와주세요~~~

  • shinhj88
    shinhj88

    실험데이터 복구하기 문제를 풀고 있는데
    여러 테스트 데이터를 넣어 보았는데 잘못된점을 찾지 못하였습니다.
    고수님들이 좀 도와주세요 ㅜㅜ

    제가 푼방법은
    a배열에는 i번째 단어 다음에 j번째 단어가 왔을때 몇개의 단어가 추가 되는지를 저장하고 추가되는 문자도 함께 저장했습니다.
    그다음 외판원문제처럼 총 길이가 최소가 되도록 하는 경로를 구하였습니다.
    글쓰는것에 서툴러서 제가 푼 풀이가 잘 전달됬는지 모르겠습니다.ㅠㅠ
    도와주세요ㅠㅠ

    #include <cstdio>
    #include <cstring>
    #include <memory>
    #include <cmath>
    int n;
    struct calData{
        int velue;
        char printstring[100];
    }a[16][16],seta,data[16];
    int D[16][(1<<16)+1];
    int MAX;
    int P[16][1<<16];
    void input()
    {
        int i;
        scanf("%d",&n);
        MAX=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s",data[i].printstring);
            data[i].velue=strlen(data[i].printstring);
            MAX+=data[i].velue;
        }
        MAX++;
    }
    calData cal(calData A,calData B)
    {
        int i,j,k;
        bool flag=false;
        calData temp;
        temp.velue=0;
        temp.printstring[0]=NULL;
        //strcpy(temp.printstring,data[I]);
        for(i=0;i<A.velue;i++)
        {
            k=i;
            flag=false;
            for(j=0;j<B.velue;j++)
            {
                if(k==A.velue)break;
                if(A.printstring[k]!=B.printstring[j]){
                    flag=true;
                    break;
                }
                k++;
            }
            if(!flag)
            {
                for(k=j;k<B.velue;k++)
                {
                    temp.printstring[temp.velue++]=B.printstring[k];
                }
                temp.printstring[temp.velue]=NULL;
                return temp;
            }
        }
        temp.velue=B.velue;
        strcpy(temp.printstring,B.printstring);
        return temp;
    
    }
    void mkdata()
    {
        int i,j;
        calData t;
        for(i=1;i<=n;i++)
        {
            a[0][i]=data[i];
            for(j=1;j<=n;j++)
            {
                if(i==j)
                {
                    a[i][j].velue=0;
                    a[i][j].printstring[0]=NULL;
                    continue;
                }
                t=cal(data[i],data[j]);
                a[i][j]=t;
            }
        }
    
    }
    int TSP(int check,int now)
    {
        int i,t,m;
        if((1<<(n+1))-1==check)
        {
            return 0;
        }
        if(D[now][check]!=-1)return D[now][check];
        D[now][check]=MAX;
        for(i=1;i<=n;i++)
        {
            if(!(check&(1<<i)))
            {
                t=TSP(check+(1<<i),i);
                m=a[now][i].velue;
                for(int j=1;j<=n;j++)
                {
                    if((check&(1<<j))&&a[j][i].velue==0)
                    {
                        m=0;
                        break;
                    }
                }
                t+=m;
                if(D[now][check]>t)
                {
                    D[now][check]=t;
                    P[now][check]=i;
                }
    
            }
        }
        return D[now][check];
    }
    void output(int now,int check)
    {
        bool flag=true;
        while(1)
        {
            flag=true;
            int to=P[now][check];
            for(int i=1;i<=n;i++)
            {
                if((check&(1<<i))&&a[i][to].velue==0)
                {
                    flag=false;
                    break;
                }
            }
            check+=1<<P[now][check];
            if(flag==true)
            {
                for(int i=0;i<a[now][to].velue;i++)
                {
                    printf("%c",a[now][to].printstring[i]);
                }
            }
            now=to;
            if(check==(1<<(n+1))-1)break;
    
        }
        printf("\n");
    
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            memset(D,-1,sizeof(D));
            memset(P,0,sizeof(P));
            input();
            mkdata();
            TSP(1,0);
            output(0,1);
    
        }
    }
    


    11년 전
6개의 댓글이 있습니다.
  • JongMan
    JongMan

    한 문자열이 다른 문자열의 부분 문자열인 경우가 잘 처리되나요?


    11년 전 link
  • shinhj88
    shinhj88

    네 그걸 처리하기 위해서
    앞에 선택되어진 문자열에 다음추가될 문자열이 부분 문자열이면 TSP함수에서 a[now][i].velue를 더하는대신 0을 더하였습니다.

       m=a[now][i].velue;
                for(int j=1;j<=n;j++)
                {
                    if((check&(1<<j))&&a[j][i].velue==0)
                    {
                        m=0;
                        break;
                    }
                }
                t+=m;
    

    11년 전 link
  • JongMan
    JongMan

    입력된 단어들을 다 포함하지 않는 출력이 나오는 경우가 있는 거 같네요. 큰 데이터를 여러개 만들어서 프로그램으로 확인해 보세요.


    11년 전 link
  • shinhj88
    shinhj88

    오! 찾았습니다 ㅜㅜ
    근데 제가 잘못된 부분을 어떤식으로 찾으셨나요??


    11년 전 link
  • JongMan
    JongMan

    저지 입력에 대고 돌려봤습니다. -_-; 틀린점이 뭐였나요? ㅋㅋ


    11년 전 link
  • shinhj88
    shinhj88

    아~~ 틀린점은 경로를 구할때 경로 중간에 완전히 포함되는 문자열이 있다면 그 완전히 포함되는 문자열 다음에 나오는 경로를 출력할때 완전히 포함되는 경로를 지우는 경우가 생가셔 오답이 나왔었습니다.
    예를 들어 a abc abd이런 데이터일때 abcabd가 답인데 abcbd이렇게 나왔습니다 즉 경로가 2 1 3인데 2 1경로까지는 문제가 안되는데 1 3 인경우 a를 제외하고 bd가 출력되는데 a는 두번째 문자열의 완전히 포함되는 단어이기때문에 문제가 되서 경로를 저장하는 배열을 수정하여 해결 하였스빈다. ㅋㅋㅋㅋㅋㅋ 글로쓰기 힘드네요 ㅋㅋㅋ 좋은책 써주신 종만님 존경합니다.ㅋㅋㅋㅋㅋ


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