BOJ 2848 알고스팟어

사용한 알고리즘

위상정렬

알고리즘 설명

구성된 사전이 올바른지 판단한 뒤에 사전의 알파펫 순서를 출력하여야 한다.
사전의 N개의 단어가 순서대로 주어지므로 이 사전의 알파펫 순서를 알아낼 수 있다.
예를 들어 “ula” 뒤에 “uka”가 등장한 경우 ‘l’ < ‘k’ 임을 알 수 있다.
위를 이용하여 각 단어에 대한 그래프를 구성한다.
단어를 구성하는 과정에서 불가능한 경우를 처리한다. ex) “luak” 뒤에 “lua” 와 같은 경우 “!”출력
Queue에 indegree가 없는 노드를 넣고 BFS를 진행한다.
여기서 Queue의 크기가 2 이상인 경우는 알파펫 순서가 애매한 경우이므로 “?”를 출력한다.
정렬이 끝나고 “!”와 “?”가 아닌 경우 위상정렬의 결과를 출력한다.

풀이

// baekjoon 2848 yechan
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N=101;
const int MAX_L=11;
const int MAX_ALPHA=26;

int N, K, indeg[MAX_ALPHA], ret[MAX_ALPHA];
char dict[MAX_N][MAX_L];
vector<int> adj[MAX_ALPHA];
bool visited[MAX_ALPHA];

int main() {
  scanf("%d", &N);
  for (int i=0; i<N; i++) {
    scanf("%s", dict[i]);
    for (int j=0; dict[i][j]; j++) {
      if (visited[dict[i][j]-'a']) continue;
      // 사전이 사용하는 알파펫 visited 체크
      visited[dict[i][j]-'a']=true;
      // 사전이 사용하는 알파펫 개수
      K++;
    }
  }

  bool impossible = false;
  for (int i=0; i<N; i++) {
    for (int j=i+1; j<N; j++) {
      for (int k=0; dict[i][k]; k++) {
        if (dict[i][k] == dict[j][k]) continue;
        if (dict[j][k] == '\0') {
          // 불가능한 조건
          impossible=true;
          break;
        }
        // 알파펫 간 관계 정의
        adj[dict[i][k]-'a'].push_back(dict[j][k]-'a');
        indeg[dict[j][k]-'a']++;
        break;
      }
    }
  }

  queue<int> q;
  for (int i=0; i<MAX_ALPHA; i++) {
    if (!visited[i]) continue;
    if (!indeg[i]) {
      q.push(i);
    }
  }

  bool arbitary = false;
  for (int i=0; i<K; i++) {
    // Cycle 조건으로 indegree가 0이 되지 않는다.
    if (q.empty()) {
      impossible=true;
      break;
    }
    int cur = q.front();
    q.pop();
    // pop전의 Queue의 크기가 2이상인 경우
    if (q.size()) arbitary=true;
    else ret[i]=cur;

    for (int j=0; j<adj[cur].size(); j++) {
      // indegree가 0인 경우 Queue에 push
      if (--indeg[adj[cur][j]] == 0) {
        q.push(adj[cur][j]);
      }
    }
  }
  if (impossible) {
    puts("!");
  } else if (arbitary) {
    puts("?");
  } else {
    for (int i=0; i<K; i++)
      printf("%c", ret[i]+'a');
    puts("");
  }
  return 0;
}