백준저지 1013번 Contact & 2671번 잠수함 식별 풀이

백준저지 1013번 문제 Contact과 2671번 문제 잠수함 식별은 문제가 똑같다.

특정한 문자열 패턴에 일치하는지 확인하는 문제이다. 문자열 패턴이 정규표현식(Regular Expression) 형태이므로 DFA(Deterministic Finite Automata)를 그려서 O(n)에 문제를 해결할 수 있다.

주어진 패턴이 (100+1+|01)+인데, DFA를 바로 그리기에는 어려우므로 NFA(Non-deterministic Finite Automata)를 먼저 그린다. 이후 DFA로 변환해보도록 한다.

아래 그림은 NFA를 그린 것이다. Initial State는 a이고, Final State는 e, g이다.

이후 DFA로 변환하면 다음과 같다. 똑같이 Initial state는 a이고 Final State는 g, e, {b,e} 이다.

state를 빨간샛 숫자에 맞추어 번호를 부여한 뒤 구현하면 다음과 같은 코드가 나타난다.

1013번 Contact 문제 풀이 코드이다.

 

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

#define FAIL 9
const int tr[10][2] = {
    {5, 1}, //0
    {2, FAIL}, //1
    {3, FAIL}, //2
    {3, 4}, //3
    {5, 7}, //4
    {FAIL, 6},//5
    {5, 1},//6
    {8, 7},//7
    {3, 6},//8
    {FAIL, FAIL}//9
};

bool chk(string &seq) {
    int state = 0;
    for (size_t i=0; i < seq.size(); i++) {
        char ch = seq[i] - '0';
        state = tr[state][ch];
    }
    return state == 4 or state == 6 or state == 7;
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        string seq;
        cin >> seq;
        bool ans = chk(seq);
        cout << (ans ? "YES" : "NO") << '\n';
        
    }
	return 0;
}

잠수함 식별 문제도 거의 동일한 코드로 풀이가 가능하다. 하지만 2671번 잠수함 문제는 C++에서 제공하는 정규표현식 라이브러리를 이용해서 풀이해보겠다.

 

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

int main() {
    regex re("(100+1+|01)+");    
    cmatch m;
    string seq;
    cin >> seq;
    bool ans = regex_match(seq.c_str(), m, re);
    cout << (ans ? "SUBMARINE" : "NOISE") << '\n';

	return 0;
}

위와 같은 간단한 코드로 쉽게 정규표현식에 일치하는지 확인할 수 있다.

정규표현식이 정확한지는 다음 사이트에서 쉽게 태스트 해 볼 수 있다.

https://regexr.com/