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는 두번째 문자열의 완전히 포함되는 단어이기때문에 문제가 되서 경로를 저장하는 배열을 수정하여 해결 하였스빈다. ㅋㅋㅋㅋㅋㅋ 글로쓰기 힘드네요 ㅋㅋㅋ 좋은책 써주신 종만님 존경합니다.ㅋㅋㅋㅋㅋ


    10년 전 link

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