글 읽기 - 어떤 케이스에서 나가는지 잘 모르겠습니다.

plzrun 7년 전 0

bfs 위상정렬로 구현했습니다.

위상정렬 하던도중 큐가 완전히 비게 되면 !

큐 사이즈가 2이상이 되면 ?

무사히 다 통과하면 위상정렬이 완료된 것으로 하였습니다.

근데 어디가 문제일까요 ㅠㅠ?

도와주세요 ㅠㅠ

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
using namespace std;
vector<int> ans, v[26];
set<int> valid;
string s[101];
int in[26];
int chg(char c) { return c-'a'; }
queue<int> q;
int main() {
    int n; cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> s[i];
        
        //나온 글자를 전부 체크한다.
        for(int j=0; j<s[i].size(); j++) valid.insert(chg(s[i][j]));

        if(i==1) continue;
        
        //DAG 만들기
        int lim = min((int)s[i-1].size(), (int)s[i].size());
        for(int j=0; j<lim; j++) {
            if(s[i-1][j]!=s[i][j]) {
                int pc=chg(s[i-1][j]), c=chg(s[i][j]);
                v[pc].push_back(c);
                in[c]++;
                break;
            }
        }
    }
    for(int i=0; i<26; i++) {
        if(!in[i]&&valid.count(i)) q.push(i);
    }
    int lim=valid.size();
    for(int i=0; i<lim; i++) {
        if((int)q.size()>=2) { puts("?"); return 0; } //위상정렬된 경로가 유일하지 않은 경우
        if(q.empty()) { puts("!"); return 0; } //DAG가 아닌 경우
        
        int x=q.front(); q.pop();
        ans.push_back(x);
        for(int y: v[x]) {
            if(--in[y]==0) q.push(y);
        }
    }
    if(!q.empty()) { puts("!"); return 0; }
    for(auto &p: ans) printf("%c",p+'a');
    return 0;
}

plzrun 7년 전 2

doju님이 알려주셔서 풀 수 있었습니다.
혹시 계속 틀리는데 왜 틀리는지 이해가 안가시는 분들을 위해 테케를 남겨드리자면,

2
abc
ab

이걸 잘 처리하는지 한번 봐보세요.
s[i-x]에 해당하는 스트링이 s[i] 스트링과 prefix가 겹치는데 s[i-x]의 길이가 더 큰경우 반드시 !를 출력해야 해요.
그런데 저 같은 경우는 위/아래 단어만 비교하면서 그래프를 만들었더니 문제가 생겼네요.

pwr2011 4년 전 2

안녕하세요 궁금한게 있어서 답글을 답니다

2
abc
ab

이런 input이 들어올 수 있다고 하셨는데, 문제의 설명에서 사전순으로 정렬된 input이 들어온다고 했습니다.

저건 사전순으로 들어온게 아니지 않나요? 예를 들어 배 -> 배편 으로 사전이 정렬되어지지 배편->배 순서로 정렬이 되지는 않는것 처럼요.

감사합니다.

parkpkww 4년 전 0

" 올바른 순서가 없다면 "!"를, 가능한 순서가 한 개 이상이라면 "?"를 출력한다. "라고 문제를 주고 있습니다.

즉, 배편 -> 배 순서로 입력이 주어지는 경우 "!" 를 출력해주면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 케이스에서 나가는지 잘 모르겠습니다.

plzrun 7년 전 0

plzrun 7년 전 2

pwr2011 4년 전 2

parkpkww 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말