[알고리즘] 오토마타, 백준 1013

개발개발·2022년 11월 26일
0

문자열이 조건을 충족시키는지 확인하는 문제였다. 정규식만 알고 있다면 쉽게 풀 수있는 문제였다. 정규식 말고 다른 방법이 없을까 다른 사람들의 풀이를 찾던 중 재밌는 방법을 발견해서 공부겸 글을 작성해본다.

그 방법은 바로 Deterministic Finite Automata이다. Automata 앞에 Deterministic과 Finite이 있느 것을 보면 비결정적이고 무한한 Automate도 있는 것 같아서 살펴보았지만 공부의 깊이가 깊어지는 것 같아서 다음에 살펴보기로 기약했다.

Automata는 특정 상태에서 어떤 값에따라 다른 상태로 변화하는 것을 정리한다.

A 상태에서 0 또는 1 값을 받으면 다음으로 어떤 상태로 변이하는지 나타낸 그림이다. 마지막 상태값이 0,3,6,7 인 경우만 조건을 만족하고 있다.

package com.test.backjun;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Pattern;

public class Baek1013 {
    // 1. 정규식으로 푸는 방법
    // 2. 오토마타 ? 처음 듣는 방법, 문자열을 하나씩 읽어나가며서 상태를 바꾼다. 모로가도 안되는 상태가 되면 끝...
    public static void main(String[] args) throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//        (100+1+ | 01)+
//        regex(reader);
        automata(reader);
    }
    // 1. 정규식
    public static void regex(BufferedReader reader) throws Exception{
        int n = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        Pattern p = Pattern.compile("^(100+1+|01)+$");

        for (int i = 0; i < n; i++) {
            String v = reader.readLine();
            if(p.matcher(v).matches()){
                sb.append("yes");
            }else{
                sb.append("no");               
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    // 2. DFA
    public static void automata(BufferedReader reader)throws Exception {
        int n = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        // auto의 첫번째 array는 상태값
        // auto의 상태값 안의 값은 입력값에 따른 다음 상태로 전이할 상태값
        // 조건에 부합하지 않는 문자열은 -1 반환
        int[][] auto = new int[][]{
            {1,2},// 상태 0
            {-1,3},// 상태 1
            {4,-1},// 2
            {1,2},// 3
            {5,-1},// 4
            {5,6},// 5
            {1,7},// 6
            {8,7},// 7
            {5,0},// 8
        };
        for (int i = 0; i < n; i++) {
            String v = reader.readLine();
            int state =0 ;
            for (int j = 0; j < v.length(); j++) {
                state = auto[state][v.charAt(j)-'0'];
                if (state <0){
                    break;
                }
            }
            if(state ==0|| state ==3 || state==6 || state==7){
                sb.append("YES");
            }else{
                sb.append("NO");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

}

참고 자료들
https://maivve.tistory.com/208
https://velog.io/@haribo/%EB%B0%B1%EC%A4%80-1013-Contact

DFA, NFA 등 추가적으로 공부할 내용들
https://sweetdev.tistory.com/910
https://dokhakdubini.tistory.com/451

profile
청포도루이보스민트티

0개의 댓글