DICTIONARY 질문이요! ㅠㅠ sujae03 #include <iostream> #include <stack> using namespace std; stack <int> s; char arr1[1][22] = {'0',}; char arr2[1][22] = {'0',}; int graph[26][26] = {0,}; //초기화 필요 int N; // 단어의 개수 int visit[26] = {0,}; //초기화 필요 int VisitCheck[26]= {0,}; // 초기화 필요 int StackCheck[26]= {0,}; // 초기화 필요 char result[26] = {'0',}; // 초기화 필요 int res_pos = 0; int check = 0; //초기화 필요 void input(){ int temp =0; int temp2 = 0; int init = 1; for(int j=0; j<N; j++){ cin >> arr1[0]; if(init == 0){ for(int k=0; k<21;k++){ if(arr1[0][k] != arr2[0][k]){ //문자를 비교해봤는데 다르면, arr2가 오기전에 arr1의 값이 나와야한다. 항상 if(arr1[0][k]!=0 && arr2[0][k]!=0){ graph[arr1[0][k]-97][arr2[0][k]-97] = 1; } break; } } } init = 0; int kk=0; while(arr1[0][kk]!=0){ arr2[0][kk] = arr1[0][kk]; kk++; } } } void dfs(int v){ if(VisitCheck[v]){return;} s.push(v); while(!s.empty()){ v=s.top(); for(int j=0; j<26; j++){ if(graph[v][j] == 1 && !visit[j]){ if(StackCheck[v]){ check = 1; return ; } StackCheck[v] = 1; s.push(j); v = j; break; } if(j ==25){ visit[v] = 1; VisitCheck[v] = 1; for(int k=0; k<26; k++){ if(result[k] == v+97){ check = 1; // 1이 되면 순환이 생겼다는 의미 break; } } if(check == 0){ result[res_pos++] = v+97; } s.pop(); } } } } void init(){ while(!s.empty()){ s.pop(); } res_pos = 0; check = 0; for(int i=0; i<26;i++){ for(int j=0; j<26; j++){ graph[i][j] = 0; } visit[i] = 0; result[i] = '0'; VisitCheck[i] = 0; StackCheck[i] = 0; } } int main(){ int test_case =0; cin >>test_case; // test_case 개수 입력받기 for(int i=0 ; i<test_case; i++){ cin >> N; //단어의 개수는 1000개까지 입력 가능하다. input(); check = 0; for(int j=0; j<26; j++){ dfs(j); } if(check == 1){ cout<<"INVALID HYPOTHESIS"; } else{ for(int j=0; j<26; j++){ cout<<result[j]; } } cout<<endl; init(); //초기화 } return 0; } 도저히 반례를 못찾겠네요 ㅠㅠ 왜 오답이죠 ??? 8년 전
1개의 댓글이 있습니다. JongMan 알고리즘 설명을 덧붙여 주시지 않으면 답변이 어렵습니다. 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
sujae03
8년 전