BOJ 2671 잠수함 식별

ㅎㅇ! 오랜만에 돌아왔다.
오늘의 문제는 KOI 1996의 중등 2번이자 고등 1번인, 잠수함 식별이다.

풀이법은 양심에 찔리지만 간단한 풀이와 정직하지만 귀찮은 풀이로 총 두 가지 풀이를 소개하고자 한다.
두 풀이의 차이점은 단순히 구현 방식의 차이일 뿐, 기본적 원리의 차이는 없다.

우선, 문자열의 길이가 길지 않아서 백트래킹으로 AC를 받아낼 수 있을지는 모르겠다.(시도해본 관리자가 있다면 코멘트 부탁한다.)
이 글에서는 깔끔하고 감탄할 수 있는 풀이를 소개한다.

1. std::regex를 활용하자.

잠수함의 엔진 소리는 (100₁|01)~으로 나타낼 수 있다. 각 기호의 정의를 살펴보면, 정규식 (100+1+|01)+과 완전히 일치함을 알 수 있다.
C++의 regex 객체와 regex_match 함수를 활용하면 다음과 같은 코드를 작성할 수 있다.

/*
Sol1. 정규표현식을 활용한다.
디스크립션의 (100~1~|01)~는 정규표현식 (100+1+|01+)+와 일치한다.
*/
#include<bits/stdc++.h>
using namespace std;

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

2. FSM을 활용하자.

문제를 해결할 때 존재하는 상태가 적당한 수만큼 존재하고, 각 상태들 사이의 전이를 통해 문제를 해결할 수 있다면 FSM(유한상태기계. 날아다니는 스파게티 괴물이 아니다.)을 작성해 문제를 해결할 수 있다.
이 잠수함 식별이라는 문제 또한 상태의 개수가 매우 적고, 각 상태들 사이의 전이를 통해 문제를 해결할 수 있다.
우선 다음은 이 문제에서 등장할 수 있는 상태들이다.
(주어진 정규식에서 ~를 T로 바꿔 (100T1T|01)T라고 생각하자. 마크다운 아무리 굴려봐도 모르겠다.)

Initial: 아무 것도 읽지 않았을 때의 더미 상태이다. 구현상의 편의를 위해 추가하였다.
A: (100T1T|01)T.
B: (100T1T|01)T.
C: (100T1T|01)T.
D: (100T1T|01)T. 100+1+ 조각의 완결 상태이다.
E: (100T1T|01)T. 01 조각의 완결 상태이다.
Initial, A, B, C, D, E에 각각 1,2,3,4,5,6의 번호를 매기고 이를 이용해 비트마스킹을 할 것이다. (반드시 필요한 작업은 아니다.)
이 상태들에 대한 FSM을 그려보면 다음과 같이 그릴 수 있다.

원은 각 상태를 의미하고, 선과 그 위의 텍스트박스는 전이와 전이에 필요한 입력을 의미한다.
이 FSM을 코드로 옮겨 ST(i)를 문자열의 i번째 인덱스까지 읽었을 때 가능한 상태를 비트마스킹한 결과로 정의하면 다음과 같은 코드를 작성할 수 있다.

/*
Sol2. FSM을 활용한다.
FSM을 작성하여 이에 맞게 상태를 전이시킨다. 본 코드에서는 비트마스킹을 추가로 활용하였으나 반드시 필요한 것은 아니다.
입력의 끝까지 읽어들였을 때 가능한 상태가 존재한다면 SUBMARINE, 아니면 NOISE이다.
*/
#include<bits/stdc++.h>
using namespace std;

int st[999];//FSM BitMasking

int main(void){
	string s;
	cin>>s;
	s+="|";//Prevent SegmentFault
	st[0]=1; //Bin : 0 0 0 0 0 1
	for(int i=0;i<s.size()-1;i++){
		if(st[i]&1){//State 'Initial'
			if(s[i]=='1')st[i+1]|=2;                //Bin: 000010
			if(s[i]=='0'&&s[i+1]=='1')st[i+2]|=32;  //Bin: 100000
		}
		if(st[i]&2){//State 'A'
			if(s[i]=='0')st[i+1]|=4;                //Bin: 000100
		}
		if(st[i]&4){//State 'B'
			if(s[i]=='0')st[i+1]|=8;                //Bin: 001000
		}
		if(st[i]&8){//State 'C'
			if(s[i]=='0')st[i+1]|=8;                //Bin: 001000
			if(s[i]=='1')st[i+1]|=16;               //Bin: 010000
		}
		if(st[i]&16){//State 'D'
			if(s[i]=='1')st[i+1]|=18;               //Bin: 010010
			if(s[i]=='0'&&s[i+1]=='1')st[i+2]|=32;  //Bin: 100000
		}
		if(st[i]&32){//State 'E'
			if(s[i]=='1')st[i+1]|=2;                //Bin: 000001
			if(s[i]=='0'&&s[i+1]=='1')st[i+2]|=32;  //Bin: 100000
		}
	}
	cout<<((st[s.size()-1]&48)?"SUBMARINE":"NOISE");
}