2671 - 잠수함 식별

https://www.acmicpc.net/problem/2671

http://59.23.113.171/30stair/submarine/submarine.php

오토마타로 해결한다는 힌트를 듣고 오토마타가 뭔지 찾아서 문제의 오토마타를 나름대로 그려보았다.

얼추 되는 거 같지만 10001100001 와 같은 예는 식별하지 못한다.

그래서 100+ 이후의 1+ 에 대해서 상태를 추가해서 좀더 세밀하게 만들었다.

오토마타를 처음 접했는데, 뭔가 그래프의 인접행렬과 유사한 느낌인 것 같아서 새로웠다.

위의 그림은 노트에 끄적거린 것을 그대로 옮긴거라 좀 정리가 안되어있다.

처음에는 7번 상태 없이, 5번 상태에서 1인 경우 다시 5번으로 돌아와 1+ 를 나타내려 했는 데 엉망이였다. 1이 조금만 반복해도 맞다고 되어버렸다.

1+ 의 형태를 반복하다가 0 이 나오면 새로운 100+ 패턴인지 01 로 끊어지는 패턴인지 구분할 수 있도록 7번 상태를 추가했더니 잘 돌아갔다.

빨간색 화살표는 식별을 못하는 FAIL 상태이고, 초록색 상태는 패턴이 올바르게 끝난 상태이다.

동일한 문제

1013 - Contact

#include <cstdio>

#define ROOT 0
#define FAIL 8

int jump[9][2]={
    // [0] 일 때 가는 경우, [1] 일 때 가는 경우
    {1, 2},
    {FAIL, ROOT},   // -0
    {4, FAIL},      // -1
    {6, ROOT},      // 1001-1001 의 구분점
    {6, FAIL},      // -10-
    {1, 7},         // 100-1
    {6, 5},         // -100+
    {3, 7},         // -1+
    {FAIL, FAIL}
};

bool isRight(int pos){
    return (pos == ROOT || pos == 5 || pos == 7);
}

int main(){
    int i, j, n;
    char s[205]={};
    while(~scanf("%s ", s)){
        int curPos = ROOT;
        for(i=0; s[i]; ++i){
            curPos = jump[curPos][s[i]-'0'];
            if(curPos == FAIL) break;
        }
        puts(isRight(curPos)?"SUBMARINE":"NOISE");
    }
    return 0;
}