BOJ 18109 - 도깨비불 (오토마타 풀이)

boj-18109-automata.cpp

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

#define CONSO     0
#define VOWEL     1
#define COMBINE_C 2
#define COMBINE_V 3

bool isVowel[255];
set<string> cVowel, cConso;

string cc[] = { "rt", "sw", "sg", "fr", "fa", "fq", "ft", "fx", "fv", "fg", "qt" };
string cv[] = { "hk", "ho", "hl", "nj", "np", "nl", "ml" };

#define _     0
#define _K    1
#define _KA   2
#define _KK   3
#define _KAK  4
#define _KAKK 5

// next_state[prev_state][type]
int next_state[6][4] = {
    {_K, _, -1, -1},
    {_K, _KA, _KK, -1},
    {_KAK, _, -1, _KA},
    {_K, _KA, -1, -1},
    {_K, _KA, _KAKK, -1},
    {_K, _KA, _K, -1}
};

int new_state(int state, char *s, int i) {
    int type = isVowel[s[i]] ? VOWEL : CONSO;
    if (i > 0 && cVowel.count({ s[i - 1], s[i] })) type = COMBINE_V;
    if (i > 0 && cConso.count({ s[i - 1], s[i] })) type = COMBINE_C;

    int ret = next_state[state][type];
    // can not be stop consonant(받침)
    if (ret == _KAK && (s[i] == 'Q' || s[i] == 'W' || s[i] == 'E')) ret = _K;
    return ret;
}

int solve(char *s) {
    int ans = 0, state = _;
    for (int i = 0; s[i]; ++i) {
        int next = new_state(state, s, i);
        // count edge which _KAK --> _KA
        ans += (state == _KAK || state == _KAKK) && next == _KA;
        state = next;
    }
    return ans;
}

int main() {
    for (auto& x : "yuiophjklbnmOP") isVowel[x] = true;
    for (auto& x : cc) cConso.insert(x);
    for (auto& x : cv) cVowel.insert(x);

    char s[10001];
    int ret = 0;
    while (~scanf("%s ", s)) {
        ret += solve(s);
    }
    printf("%d\n", ret);

    return 0;
}