[도전 13일차] 잠수함 식별 - KOI 고등부 풀이

※복습 : 

문제 : BOJ 2671 잠수함 식별

잠수함

문제 링크

 

사용 알고리즘 : 오토마타 이론

 

풀이: 

 

문제를 읽어보자.

주어진 이진문자열이 (100~1~|01)~ 의 패턴을 가지는지 식별해야 한다.

 

처음 접근으로는 문자열의 처음부터 살펴보면서 처음에 1이면 그 후에 100~1~ 의 패턴을 가지는지 검사, 0이면 01인지 검사, 이런식으로 쭉쭉 나아가는 방법이 있다. 

한번 상상해보자 벌써 무수히 많은 if문의 향연이 상상되지 않는가? 

 

상태를 체계적으로 결정하는 것이 바로 오토마타를 이용한 매칭이다.

 

오토마타 이론은 상태 간 연관 관계를 이용하여 변환 후 최종 상태를 결정할 때 이용할 수 있다.

 

순서도와 비슷해 보인다. 

 

ㅎㅎㅎ

힘듦과 행복이라는 상태간 연관 관계를 표시해 보았다.

오토마타가 무엇인지 알았으니, 이제 문제의 패턴을 오토마타로 나타내어 보자.

 

처음에 0과 1을 이용해 상태를 구별했던 것에서 부터 출발한다.

 

초기 상태는 아무것도 없는 상태다.

그 상태에서 0과 1을 추가할 수 있다. 그럼 이제 '0'이란 상태와 '1'이란 상태가 있다.

'0'에서는 0을 추가하면 '00'이란 패턴이 되고, 이는 불가하므로 ( 문자열 초반부라는 사실을 명심하자.)  반드시 '01' 이 되어야 한다.

'1'에서는 이와 마찬가지로 0을 추가해야 한다.

이런 식으로 각각의 상태에 대하여 관계를 나타내는 것이다.

 

 

그림의 8번 상태에 주목하자. 

손그림!

7번, 100~1~ 상태에서 우리가 마지막으로 끝나는 1이 새로운 100~1~ 패턴의 시작을 알리는 것인지, 아니면 그 다음에 01 패턴이 시작하는 것인지 구분하는 방법의 Key는 바로 8번 상태다.

 

C/C++의 '배열'을 이용하여 상태간 전이를 쉽게 수행할 수 있다.

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end())
const int INF = 1e9;
using namespace std;
int n;
string s; 
const int F = 9;
int chg[10][2]={
{1,3},{F,2},{1,3},{4,F},{5,F},{5,6},{1,7},{8,7},{5,2},{9,9}
//0     1     2     3     4     5     6    7    8
};
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>s;
    int n=0;
    for(char&c : s){
        n=chg[n][c&15];
        if(n==F) break;
    }
    cout<<((n==2||n==6||n==7)?"SUBMARINE":"NOISE");
}

 

*오토마타 문제는 친구랑 같이 풀었는데, 답지에서 만족한 나를 비슷한 유형 평정으로 응용력 향상의 길로 이끌어준 친구다.

 

다음은 함께 풀어보면 좋은 문제들이다.

 

BOJ 소변기

Codeup 3의 배수 판별하기 (More)

 

 

궁금한 점이 있으시다면 질문 남겨주세요:)