DICTIONARY

  • dexaboud3
    dexaboud3
    #include<iostream>
    #include<vector>
    #include<string>
    #include<algorithm>
    
    using namespace std;
    
    vector<vector<int>> adj; //인접행렬
    vector<string> s;//string을 넣는 vector
    vector<int> seen;//방문 여부
    vector<int> list;
    
    void dfs(int here) {//dfs탐색
        seen[here] = 1;
        for (int i = 0; i < adj.size(); i++) {
            if (adj[here][i] && !seen[i])
                dfs(i);
        }
        list.push_back(here);//방문한것을 list에 넣는다.
    }
    
    vector<int> dfsAll(void) {//컴포넌트를 모두 순회하기 위해서.
        int n = adj.size();
        seen = vector<int>(n, 0);//초기화를 진행한다(오버라이딩)
        list.clear();
        for (int i = 0; i < n; i++)
            if (!seen[i])
                dfs(i);
        reverse(list.begin(), list.end());
    
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (adj[list[j]][list[i]]) return vector<int>();
            }
        }
        return list;
    }
    
    /*인접 행렬을 만드는 부분*/
    void makegragh(const vector<string>& words) {
        adj = vector<vector<int>>(26, vector<int>(26, 0));//그래프 초기화를 실행
    
        for (int i = 1; i < words.size(); i++) {//j,i
            int j = i - 1;
            int len = min(words[i].size(), words[i].size());
            for (int k = 0; k < len; k++) {
                if (words[i][k] != words[j][k]) {
                    int a = words[j][k] - 'a';
                    int b = words[i][k] - 'a';
                    adj[a][b] = 1;
                    break;
                }
            }
        }
    }
    
    
    
    int main(void) {
        int T;
        int n;
        vector<int> l;
        cin >> T;
        for (int i = 0; i < T; i++) {
            //초기화 공정
            adj.clear();
            s.clear();
            l.clear();
            cin >> n;
            s = vector<string>(n);
            for (int j = 0; j < n; j++) {
                cin >> s[j];
            }
            makegragh(s);
            l = dfsAll();
            if (l == vector<int>())
                cout << "INVALID HYPOTHESIS" << endl;
            else {
                for (int k = 0; k < 26; k++)
                    cout << (char)(l[k]+'a');
                cout << endl;
            }
        }
        return 0;
    }
    
    (C++ 소스 코드)
    

    DICTIONARY문제인데요....

    혼자공부하면서 원리이해하고, 책에있는내용을 다시 치면서
    맞나 하면서 올려봤는데 계속 RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow)가 뜨네요....
    제 컴퓨터에서는 잘돌아가지만... 올리면 계속 같은 메세지가
    떠서... 왜그러는지 혹시 아시면 조언 부탁드리겠습니다.


    8년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan
    int len = min(words[i].size(), words[i].size());

    여기 버그가 있네요.


    8년 전 link
  • dexaboud3
    dexaboud3

    우아.... 정말 감사합니다.. 저는 바보인가바요... ㅠㅠ


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