으헝헝 .. dictionary 질문드려봐요 ㅠㅠ

  • skan1543
    skan1543

    전체적인 아이디어는 책하고 비슷합니다아..

    DFS를 돌면서 가장 먼저 DFS가 종료되는 노드들을 스택에 추가하고.. 모든 DFS가 종료되었을때 역순으로 출력해줬는데요.

    사이클의 경우엔, 경로들을 비트마스크 하여.. DFS의 인자로 전달해서 . 현재 노드에서 갈 수 있는 노드중에, 이미 지나온 노드가 있다면 사이클이 있다고 판단하였습니다.

    어디가 문제인지 조금만 봐주시면 감사하겠습니다. (_ _)

    #include<stdio.h>
    #include<vector>
    #include<string.h>
    #include<string>
    #include<stack>
    
    using namespace std;
    
    bool check[30][30];
    bool visited[30];
    stack<int> pathh;
    
    bool DFS(int now, int path)
    {
        visited[now] = true;
        path += (1 << now);
    
        for (int i = 0; i < 26; i++)
        {
            if (check[now][i] == 1 && (path &(1 << i))>0)
                return false;
            else if (check[now][i] == 1 && visited[i] == false)
                if (DFS(i, path)== false) return false;
        }
        pathh.push(now);
        return true;
    }
    int main()
    {
        freopen("input.txt", "r", stdin);
    
        int t;
        scanf("%d", &t);
        while (t--)
        {
            for (int i = 0; i < 30; i++)
            {
                visited[i] = 0;
                for (int j = 0; j < 30; j++) check[i][j] = 0;
            }
    
            int n;
            scanf("%d", &n);
    
            char temp[1001][30];
            for (int i = 0; i < n; i++)
                scanf("%s", temp[i]);
    
            for (int i = 0; i < n - 1; i++)
            {
                int idx = 0;
                while (idx < strlen(temp[i]) && idx < strlen(temp[i + 1]))
                {
                    if (temp[i][idx] == temp[i + 1][idx]) idx++;
                    else
                    {
                        check[temp[i][idx] - 'a'][temp[i + 1][idx] - 'a'] = 1;
                        break;
                    }
                }
            }
    
    
            vector<int> canstart;
    
            for (int i = 0; i < 26; i++)
            {
                int j,l=0;
                for (j = 0; j < 26; j++)
                {
                    if (check[i][j] == 1) l++;
                    if (check[j][i] == 1) break;
                }
                if (j == 26 && l!=0) canstart.push_back(i);
            }
    
            if (canstart.empty()){
                printf("INVALID HYPOTHESIS\n");
                continue;
            }
    
    
            int i;
    
            for (i = 0; i < canstart.size(); i++)
                if (DFS(canstart[i], 0) == false) break;
    
    
            if (i != canstart.size()) {
                printf("INVALID HYPOTHESIS\n");
                continue;
            }
    
            while (!pathh.empty()) {
                printf("%c", pathh.top() + 'a'); pathh.pop();
            }
            for (int i = 0; i < 26; i++) if (!visited[i]) printf("%c", i + 'a');
            printf("\n");
    
    
        }
        return 0;
    }
    

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