단어 제한 끝말잇기 관련 질문 드립니다.

  • mhs4670
    mhs4670

    안녕하세요.

    최근 알고리즘 문제해결전략으로 공부하고 있는 학생입니다.

    제가 c언어를 주로 사용해서

    c언어로 구현을 해보는데..

    많은 case들을 넣어봤는데도 오답이 나오네요;;

    10시간째 안되니까 울기 직전입니다.. 하하..

    제가 왜 안되는지 이유를 생각해보려했는데

    아무리 생각해도 이유를 모르겠네요

    책이랑 완전 똑같이두 바꿔보구

    혹시 출력형식에 마지막 스페이스가 들어가면 안되는게 아닐까

    생각해서 빼보기두 하고..

    안되는 case라도 알면 그걸 보고 연구라도 하겠는데

    이상한거 넣어봐도 다 되는데 말이죠 ㅠㅠ,,

    혹시 바쁜 시간에 조금 짬을 내어 도와주실분 있으면

    감사하겠습니다..
    WORDCHAIN

    #include<stdio.h>
    #define MAX (100+10)
    int ad[26][26]; //인접행렬
    int indegree[26], outdegree[26];
    int visited[MAX];
    int stack[MAX];
    int sp = -1;
    int N;
    char word[MAX][10 + 5];
    char *string[MAX];
    int rp;
    void push(int val){ //나중에 역순으로
        stack[++sp] = val; //출력해야하기 때문에 스택으로 구현
    }                       //했습니다.
    int pop(void){
        if (sp == -1) return 0;
        return stack[sp--];
    }
    
    void makeAd(void){ //인접행렬을 만드는 부분입니다
        int i, j;
        int fir, sec;
    
        for (i = 0; i < N; i++){
            fir = word[i][0] - 'a';
            for (j = 1; word[i][j] != '\0'; j++);
            sec = word[i][j - 1] - 'a';
            ad[fir][sec]++;
            indegree[sec]++;
            outdegree[fir]++;
        }
    }
    int checkEuler(void){  //들어오고 나오는 개수를 이용하여
        //int plus=0, minus=0; //서킷,트레일이 아닌것을 거르는부분
        int i;              //입니다.
        int temp;
        int plus = 0, minus = 0;
        for (i = 0; i < 26; i++){
            temp = outdegree[i] - indegree[i];
            if (temp > 1 || temp < -1) return 0;
            if (temp == 1) {
                plus++;
            }
            if (temp == -1) minus++;
        }
        return ((plus == 1 && minus == 1) || (plus == 0 && minus == 0));
    
    }
    
    void DFS(int vertex){
        int i;
        //printf("run DFS()\n");
        for (i = 0; i < 26; i++){
            while (ad[vertex][i]>0){
                ad[vertex][i]--;
                DFS(i);
            }
        }
        push(vertex);
    }
    void getCircuit(void){   //서킷일 경우와 트레일일 경우를 나눕
        int temp;               //니다.
        int i, j;
    
        for (i = 0; i < 26; i++){
            if (outdegree[i] == indegree[i] + 1){
                DFS(i);
                return;
            }
        }
        for (i = 0; i < 26; i++){
            if (outdegree[i]){
                DFS(i);
                return;
            }
        }
    }
    
    void input(void){
        int i;
        scanf("%d", &N);
        for (i = 0; i < N; i++){
            scanf("%s", word[i]);
        }
    }
    void printWord(void){
        int i, j, last;
        int fir, sec;
        if (sp != N){
            string[rp++] = "IMPOSSIBLE";
            return;
        }
        fir = sec = pop();
        //printf("fir:%c  sec: %c\n", fir + 'a', sec + 'a');
        for (i = 0; i < N; i++){
            fir = sec;
            sec = pop();
            //printf("fir:%c  sec: %c\n", fir + 'a', sec + 'a'); 
            for (j = 0; j < N; j++){
                for (last = 0; word[j][last] != '\0'; last++);
                if (fir == word[j][0] - 'a' && sec == word[j][last - 1] - 'a' && !visited[j]){
                    visited[j]++;
                    string[rp++] = word[j];
                }
            }
        }
        //printf("\n");
    }
    void init(void){
        int i, j;
    
        rp = 0;
    
        for (i = 0; i < 26; i++){
            for (j = 0; j < 26; j++){
                ad[i][j] = 0;
            }
        }
        for (i = 0; i < 26; i++){
            indegree[i] = 0;
            outdegree[i] = 0;
        }
        for (i = 0; i < MAX; i++){
            visited[i] = 0;
            string[i] = NULL;
        }
        sp = -1;
    
    }
    int main(void){
    
        int C, i,j;
    
        scanf("%d", &C);
        for (i = 0; i < C; i++){
            input();
            makeAd();
            if (!checkEuler()) {
                string[rp++] = "IMPOSSIBLE";
            }
            if (rp == 0){
                getCircuit();
                printWord();
            }
            for (j = 0; j < rp; j++){
                printf("%s ", string[j]);
            }
            printf("\n");
            init();
        }
    
        return 0;
    }
    

    ..


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

    출판사에 이메일 주셨던 분이시죠?

    1
    10
    eshrjbt
    hjobl
    agambh
    zll
    sybjnnde
    tcutqs
    lsw
    tsnnba
    wnmebpynpz
    ejduwojt

    를 한 번 넣어 보세요.


    6년 전 link
  • mhs4670
    mhs4670

    ㅜㅜ 정말 감사합니다. 부족한 실력에 부끄러울 따름이네요;; 메모리 아끼려고 graph를 안만들고 하려다보니 이런 바보같은 결과가 나왔네요.. 감사합니다!


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