boj 2848: 알고스팟어

https://www.acmicpc.net/problem/2848

2848번: 알고스팟어

좀 양아치 문제다.

우선 크게, 

1) 사이클이 있는경우

2) 위상정렬을 하는 도중에 큐 사이즈가 2이상인 순간이 있는경우

3) 큐사이즈가 항상 1인경우

세가지로 분류할 수 있다.

1)번의 경우엔 사전에 사용된 모든 알파벳을 사용해서 큐로 그래프를 못만들기 때문에, 위상정렬시키는 order 벡터의 사이즈가 

비정상적이다. 이건 금방 캐치할 수 있다.

2)번의 경우엔 다음과 같다.

1의 ind=0이기 때문에 1 큐에 넣고 그다음에 1 꺼내서 2,3넣는다.

2,3이 동시에 들어가는데 둘이 서열이 안정해진다. 이경우엔 '?' 이다.

3)인경우는 일반적인 모든 노드의 서열이 정해지는 위상정렬이 가능한 경우이다.

 

이문제는 양아치인게, 위 경우 다 따져줘도 93%에서 끝난다.

'사전식으로 정렬된 입력'을 위배하는 경우가 input으로 들어오기 때문이다.

예를들자면,

2

ab

a 

같은 양아치 입력이 주어진다. (사전식으로 들어온다면서 이걸 위배할까 설마 했는데 역시나 그렇다.)

#include<bits/stdc++.h>
using namespace std;

vector<string> word;
int n;
bool check[26];
vector<int> node[26];
map<int,int> isUsed;
int ind[26], totalUsed;

int make_dictionary(){
  for(int i=0;i<n;i++){
    int len=word[i].length();
    for(int j=0;j<len;j++) isUsed[word[i][j]-'a']=1;
  }
  for(int i=0;i<n-1;i++){
    int minlen=min(word[i].length(),word[i+1].length());
    for(int j=0;j<minlen;j++){
      if(word[i][j]!=word[i+1][j]){
        int a = word[i][j]-'a', b = word[i+1][j]-'a';
        node[a].push_back(b);
        isUsed[a]=1;
        isUsed[b]=1;
        ind[b]++;
        break;
      }else if(j==minlen-1&&word[i+1].length()==minlen&&word[i].length()>minlen){
        return 0;
      }
    }
  }
  return 1;
}


int main(){

  cin>>n;
  word = vector<string> (n);
  for(int i = 0 ; i < n; i++){
    cin>>word[i];
  }
  int ret = make_dictionary();
  if(!ret){
    cout<<"!"<<'\n';
    return 0;
  }
  vector<int> order;
  int indZero = 0;
  queue<int> q;
  for(auto &p: isUsed){
    if(ind[p.first]==0){
      indZero++;
      q.push(p.first);
      order.push_back(p.first);
    }
  }
  if(!indZero){
    cout<<"!"<<'\n';
    return 0;
  }
  while(!q.empty()){
    int here = q.front();
    q.pop();
    int tmpindZero=0;
    for(auto &next:node[here]){
      ind[next]--;
      if(!ind[next]){
        tmpindZero++;
        indZero=max(indZero,tmpindZero);
        order.push_back(next);
        q.push(next);
      }
    }
  }
  totalUsed=isUsed.size();
  if(order.size() == totalUsed){
    if(indZero>=2){
      cout<<"?";
    }else{
      for(auto &p:order) cout<<char(p+'a');
    }
    cout<<'\n';
  }else cout<<"!"<<'\n';

  return 0;
}

기본적으로 그냥 사전에 사용된 알파벳들을 모두 inUsed에 넣어주면 된다.

사이클인지 아닌지 여부는 사전을 만들때 adj[a][b]=1 로 인접행렬을 만들고, 그냥 일단 order 위상정렬 만든 다음, 다음을 통해서도 알 수는 있다.

for(int i=0;i<order.size();i++){
  for(int j=i+1;j<order.size();j++){
    if(adj[order[j]][order[i]]) return cycle = true
  }
}