[BOJ]2671_잠수함식별

FSA문제이다.  아래 그림처럼 state를 나타내어 풀었다.

이정도만 그려두고 state D의 조금 복잡한 transition방식은 문제를 풀며 수정하였다.

 

1. state diagram

#include <iostream>
#include <vector>

using namespace std;

string solution(vector<bool> s) {
    string ans;
    char state = 'S';
    for(int i = 0 ; i < s.size() ; i ++)
    {
        bool c = s[i];
        switch (state)
        {
        case 'S':
            state = c ? 'A' : 'Z';
            break;
        case 'A':
            state = c ? 'F' : 'B';
            break;
        case 'B':
            state = c ? 'F' : 'C';
            break;
        case 'C':
            state = c ? 'D' : 'C';
            break;
        case 'D':
        {
            if (i+1 < s.size()-2)
                state = c ? (!s[i+1] && !s[i+2] ? 'A' : 'D') : 'Z';
            else
                state = c ? 'D' : 'Z';

            break;
        }
            
        case 'Z':
            state = c ? 'S' : 'F';
            break;
        case 'F':
            i = s.size();
            break;
        
        default:
            break;
        }
    }
    ans = (state == 'S' || state == 'D') ?"SUBMARINE" : "NOISE";
    return ans;
}

int main()
{
    string in;
    cin>>in;
    vector<bool> sig ;
    
    for(auto c : in)
    {
        sig.push_back(c-'0');
    }

    cout<<solution(sig)<<endl;
}

관련수업(프언, 컴파일러)을 최근에 들어 automata를 보면 state diagram을 그려야 한다는 사고방식이 뇌를 지배중이다.

이해하기는 쉽지만 별로 안 좋은 방법인 것 같다.

다른 사람들의 풀이를 보니 훨씬 좋아보인다.

 

2. Bitmasking

방식을 이 문제 검색을 통해 처음 접했는데 괭장히 간결하게 작성 할 수 있는 장점이 있는 방식인듯 하다.

하지만 잘 살펴보니 위의 방법과 idea가 거의 일치하는 것 같다. (소요되는 시간이나 머리 쓰는 정도가 동일 해 보임)

state D의 애매한 상태 (epsilon이 포함된) 를 처리하는 방식으로 1번 방식은 뒤의 여러 bit까지 보는 방식 (signal의 개수를 늘림)으로 처리했고

2.Bitmasking 방식은 그냥 state의 가지 수를 늘리는 방식으로 처리 + state 밑 transition을 2d array로 표현하여 간결하게 표현 하였다. 

이건 다음에 3.을 적용시킬 수 없는 FSA문제가 나오면 한번 시도해 보아야겠다.

 

3. std::regex , std::regex_match

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

int main(void){
	string s;
	cin>>s;
	cout<<(regex_match(s,regex("(100+1+|01)+"))?"SUBMARINE":"NOISE");
}

code 출처 - BOJ 2671 잠수함 식별 (panty.run)

문제를 보고 regular expression인줄은 알았지만 이런 함수가 있는 줄은 몰랐다.

다음에는 꼭 활용해보자.