[ 1013 ] [ DFA ] Contact

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

1013번: Contact

 

---

풀이 과정

---

1. 주어진 문제 (100+1+ | 01)+로 DFA를 구성한다.
   1. 100+1+에서 마지막에 0이 나온 경우, 100+1+로 이동할지 01로 이동할지 알수 없음.
   2. 따라서, 100+1+에서 1과 0을 추가로 만들어 주어서 1->0->0->1->1->0으로 구성
   3. 네번째 1에서 0이 나온 경우는 01로 이동, 여섯번째 0에서 0이 나온 경우는 세번째 0으로 이동하도록 DFA 구성
2. 각각의 테스트 케이스에 대하여 오토마타를 타고 넘어가본다. 이 때, 실패하는 케이스에 대해서는 바로 NO를 출력시켜 주고 다음 테스트 케이스를 진행한다.
3. 최종적으로 종료상태에 들어간 경우에만 YES를 출력해주고, 종료상태에 들어가지 않은 경우 NO를 출력시켜 준다.

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
total_case = list()
for _ in range(n):
    s = input()
    automata = 'S'
    for ch in s:
        if automata == 'S':
            if ch == '1':
                automata = 1
            else:
                automata = 2
                
        elif automata == 1:
            if ch == '1':
                print('NO')
                break
            else:
                automata = 3
                
        elif automata == 2:
            if ch == '1':
                automata = 7
            else:
                print('NO')
                break
            
        elif automata == 3:
            if ch == '0':
                automata = 4
            else:
                print('NO')
                break
            
        elif automata == 4:
            if ch == '0':
                continue
            else:
                automata = 5
                
        elif automata == 5:
            if ch == '0':
                automata = 2
            else:
                automata = 6
                
        elif automata == 6:
            if ch == '0':
                automata = 8
            else:
                continue
            
        elif automata == 7:
            if ch == '0':
                automata = 2
            else:
                automata = 1
                
        elif automata == 8:
            if ch == '0':
                automata = 4
            else:
                automata = 7
    else:
        if automata == 7 or automata == 5 or automata == 6:
            print('YES')
        else:
            print('NO')