BOJ 1013 Contact

김재섭·2021년 4월 14일

BOJ 1013 백준 백준 1013 백준 Contact

문제

아이디어

백준

목록 보기

5/10

문제

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

아이디어

원래는 정규표현식을 찾아서 배운 후 풀어보려고 했으나, 외장 모듈을 사용하지 않기 위해 오토마타 수업때 배웠던 DFA(Deterministic finite automaton)를 사용하여 풀었다.

DFA

(100+1+ | 01)+를 그린 DFA, 각 노드들은 두 개의 output이 존재해야 한다. (0, 1)
- 없다면 결과에 도달할 수 없는 경우
1번을 100+1+, 2번을 01로 생각했을 때, 1번의 1+부분이 골치아팠다.
마지막에 1이 두 개 이상 겹치면 문제인데, 1+에 의해 1이 중복되는지, 1번의 시작의 1인지 어떻게 구별해야할지 몰랐다.
그래서 질문 게시판을 참고했는데, 방법은 1이 두 번 나오는 경우를 새로운 노드로 빼자!
1이 두 번 이상 나왔을 때, 이후에 00이 나오면 1번이고, 01이 나오면 2번이다!

코드

#include <stdio.h>
#include <string.h>

int N;
char str[256];

void printfNO(void) {
    printf("NO\n");
}

void func(char str[], int index, char state) {
    //printf("index : %d, str[index] : %c, state : %c\n", index, str[index], state);
    if (strlen(str) == index) {
        if (state == 'E' || state == 'G' || state == 'F' || state == 'S') 
            printf("YES\n");
        else
            printfNO();
        
        return ;
    }
    
    if (state == 'S') {
        if (str[index] == '0') 
            func(str, index+1, 'B');
        else
            func(str, index+1, 'A');
    }
    else if (state == 'A') {
        if (str[index] == '0') 
            func(str, index+1, 'C');
        else
            printfNO();
    }
    else if (state == 'B') {
        if (str[index] == '0')
            printfNO();
        else
            func(str, index+1, 'F');
    }
    else if (state == 'C') {
        if (str[index] == '0') 
            func(str, index+1, 'D');
        else
            printfNO();
    }
    else if (state == 'D') {
        if (str[index] == '0') 
            func(str, index+1, 'D');
        else
            func(str, index+1, 'E');
    }
    else if (state == 'E') {
        if (str[index] == '1') 
            func(str, index+1, 'G');
        else
            func(str, index+1, 'B');
    }
    else if (state == 'F') {
        func(str, index, 'S');
    }
    else if (state == 'G') {
        if (str[index] == '0') 
            func(str, index+1, 'H');
        else
            func(str, index+1, 'G');
    }
    else if (state == 'H') {
        if (str[index] == '1')
            func(str, index+1, 'F');
        else
            func(str, index+1, 'D');
    }
}   

int main(void)
{   
    //freopen("input_1.txt", "r", stdin);

    scanf("%d", &N);

    while (N--) {
        scanf("%s", str);
        func(str, 0, 'S');
    }   

    return 0;
}