[BOJ] 백준 2848 알고스팟어

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

 Input 

5

ula

uka

klua

kula

al

 

 Output 

luka　

위상정렬 (Topological sort)  

위상정렬 (Topological sort)

 

문자열들의 i번째 인덱스를 비교하여 우선순위를 판별한다.

* 문자열의 접수가 같거나 포함되어 우선순위를 판별할 수 없는 경우 유의

 

① n개의 문자열에서 사용된 알파벳을 정점으로 해서,

    알파벳 간의 우선순위를 간선으로 그래프 형성

② n개 중에서 우선순위 차이가 나는 n*(n-1)/2 쌍의 문자열에 대해서 간선 생성

    위상정렬이 불가능한 경우에는 "!" 출력 (우선순위나 양방향 간선이 생기는 경우)

③ 탐색하며 우선순위대로  ans[]에 저장

    - 알파벳들 중, ans 배열에 담지 않았고, n개 문자열에서 사용되었으며, 들어오는 간선이 없는 정점 선택

    - 정점이 2개 이상인 경우에는 가능한 순서가 여러 개이므로 "?" 출력

    - 정점이 없다면 ans[] 모두 저장된 것

    - 선택된 단일 정점 u에서 출발하는 간선을 모두 삭제

④ ans[] 비어있는 경우 "?"을, 그렇지 않은 경우 ans[] 출력

 

---

#include <stdio.h>
int strlen(const char* s, int len = 0) {
    while (s[len]) len++;
    return len;
}
const int MAX_N = 100 + 5;
const int MAX_LEN = 10;
const int a2z = 26;
bool edge[a2z][a2z], used[a2z];
int cnt[a2z], ans[a2z];
char str[MAX_N][MAX_LEN + 1];
int n, len;
 
int main() {
    // freopen("input.txt", "r", stdin);
    register int i, j, k;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%s", str[i]);
        for (j = 0; j < strlen(str[i]); j++)
            used[str[i][j] - 'a'] = 1;
    }
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            for (k = 0; k < strlen(str[i]); k++) {
                if (k >= strlen(str[j])) { len = -1; break; }
                int u = int(str[i][k] - 'a');
                int v = int(str[j][k] - 'a');
                if (u == v) continue;
                if (!edge[u][v]) {
                    edge[u][v] = 1;
                    cnt[v]++;
                    if (edge[v][u]) len = -1;
                }
                break;
            }
        }
    }
    if (len < 0) {
        printf("!");
    }
    else {
        while (1) {
            int u = 0, l = 0;
            for (i = 0; i < a2z; i++)
                if (used[i] && !cnt[i]) { u = i; l++; }
            if (l > 1) len = -1;
            if (l != 1) break;
            used[u] = 0;
            ans[len++] = u;
            for (i = 0; i < a2z; i++) if (edge[u][i]) cnt[i]--;
        }
        if (len < 0) printf("?");
        if (len == 0) printf("!");
        else for (i = 0; i < len; i++)
            printf("%c", char(ans[i] + 'a'));
    }
}