#include<stdio.h>#define MAX (100+10)intad[26][26];//인접행렬intindegree[26],outdegree[26];intvisited[MAX];intstack[MAX];intsp=-1;intN;charword[MAX][10+5];char*string[MAX];intrp;voidpush(intval){//나중에 역순으로stack[++sp]=val;//출력해야하기 때문에 스택으로 구현}//했습니다.intpop(void){if(sp==-1)return0;returnstack[sp--];}voidmakeAd(void){//인접행렬을 만드는 부분입니다inti,j;intfir,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]++;}}intcheckEuler(void){//들어오고 나오는 개수를 이용하여//int plus=0, minus=0; //서킷,트레일이 아닌것을 거르는부분inti;//입니다.inttemp;intplus=0,minus=0;for(i=0;i<26;i++){temp=outdegree[i]-indegree[i];if(temp>1||temp<-1)return0;if(temp==1){plus++;}if(temp==-1)minus++;}return((plus==1&&minus==1)||(plus==0&&minus==0));}voidDFS(intvertex){inti;//printf("run DFS()\n");for(i=0;i<26;i++){while(ad[vertex][i]>0){ad[vertex][i]--;DFS(i);}}push(vertex);}voidgetCircuit(void){//서킷일 경우와 트레일일 경우를 나눕inttemp;//니다.inti,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;}}}voidinput(void){inti;scanf("%d",&N);for(i=0;i<N;i++){scanf("%s",word[i]);}}voidprintWord(void){inti,j,last;intfir,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");}voidinit(void){inti,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;}intmain(void){intC,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();}return0;}
mhs4670
안녕하세요.
최근 알고리즘 문제해결전략으로 공부하고 있는 학생입니다.
제가 c언어를 주로 사용해서
c언어로 구현을 해보는데..
많은 case들을 넣어봤는데도 오답이 나오네요;;
10시간째 안되니까 울기 직전입니다.. 하하..
제가 왜 안되는지 이유를 생각해보려했는데
아무리 생각해도 이유를 모르겠네요
책이랑 완전 똑같이두 바꿔보구
혹시 출력형식에 마지막 스페이스가 들어가면 안되는게 아닐까
생각해서 빼보기두 하고..
안되는 case라도 알면 그걸 보고 연구라도 하겠는데
이상한거 넣어봐도 다 되는데 말이죠 ㅠㅠ,,
혹시 바쁜 시간에 조금 짬을 내어 도와주실분 있으면
감사하겠습니다..
WORDCHAIN
..
7년 전