[1013] Contact

문제 출처 : https://www.acmicpc.net/problem/1013

분류 : 오토마타, 정규표현식

백준 1013 Contact

정규표현식 (100+1+|01)+ 을 만족하는 문자열을 찾아라

---

처음에 풀때는 아무 생각없이 state transition graph를 그려서 그래프를 그대로 코드로 옮기려고 하였다.

그 결과 나오게 된 코드는 아래와 같다.

종결상태와 여러 입력에 대해 state를 바꾸는 오토마타를 만든 것과 다름이 없다.

bool parse(const string& str) {
    char state = 'S';
    int len = str.length();
    for (int i = 0; i < len; i++) {
        char ch = str[i];
        switch (state) {
        case 'S':
            if (ch == '0') {
                state = 'A';
            }
            else if (ch == '1') {
                state = 'B';
            }
            else return false;
            break;
        case 'A':
            if (ch == '1') {
                state = 'S';
            }
            else return false;
            break;
        case 'B':
            if (ch == '0') {
                state = 'C';
            }
            else return false;
            break;
        case 'C':
            if (ch == '0') {
                state = 'D';
            }
            else return false;
            break;
        case 'D':
            if (ch == '0') {
                state = 'D';
            }
            else if (ch == '1') {
                state = 'E';
            }
            else return false;
            break;
        case 'E':
            if (ch == '0') {
                state = 'A';
            }
            else if (ch == '1') {
                state = 'F';
            }
            else return false;
            break;
        case 'F':
            if (ch == '0') {
                if (i + 1 < len) {
                    if (str[i + 1] == '1') {
                        state = 'A';
                    }
                    else if (str[i + 1] == '0') {
                        state = 'C';
                    }
                    else return false;
                }
                else {
                    return false;
                }
            }
            else if (ch == '1') {
                state = 'F';
            }
            else return false;
            break;
        }
    }
    return (state == 'S' || state == 'E' || state == 'F');
}
int main() {
    int N; cin >> N;
    while (N--) {
        string str; cin >> str;
        if (parse(str)) {
            cout << "YES\n";
        }
        else
            cout << "NO\n";
    }
}

그런데 사실 직관적이긴 하나 그리 좋은 풀이는 아닌 것 같다.

물론 속도적인 측면에서 빠를 수도 있겠으나... 

오토마타를 그리는것도, 그것을 코드에 옮기는 것도 실수가 발생 할 확률이 높다고 생각된다.

C++에서도 아마(제발..) 정규표현식을 다룰 수 있는 라이브러리가 있을 것 같다는 생각이 들었다.

다행히 C++11부터 다룰 수 있는 라이브러리가 있다.

(http://www.cplusplus.com/reference/regex/)

위 라이브러리를 이용하면 아래와 같은 코드로 풀이가 가능하다.

#include<iostream>
#include<regex>
#include<string>
using namespace std;
 
int main() {
    int N; cin >> N;
    while (N--) {
        string str; cin >> str;
        cout << (regex_match(str, regex("(100+1+|01)+"))?"YES\n":"NO\n");
    }
}