[백준] 1013번 - Contact

문제

<배경>

나도 재미있게 본 영화 콘택트를 배경으로 하는 문제이다.

 

<난이도>

 

<입력>

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.

그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다.

문자열 길이는 (1 ≤ N ≤ 200)의 범위를 갖는다.

 

<출력>

각 테스트 케이스에 대해 주어진 전파가 문제에서 제시한 패턴이면 “YES”를 그렇지 않은 경우는 “NO”를 출력한다.

출력 문자열은 모두 대문자로 구성되어 있다.

---

풀이

문제에서 제시한 찾아야하는 패턴은 (100+1+ | 01)+ 이다.

정규표현식을 안다면 쉽게 이해할 수 있을 것이다.

 

나는 state transition graph를 그려서 풀었다.

원래는 NFA에서 DFA로 바꿔서 그리려고 했지만 밑의 그래프도 코드로 구현이 되었기 때문에 굳이 DFA를 그리지 않았다.

오토마타를 공부하지 않은 사람들에게는 조금 어려울 수 있겠다는 생각이 들었다.

 

먼저 입력 처리를 해주었다.

시작 state는 1로 설정해준다.

check함수는 인자로 들어온 state에서 시작해서 string을 모두 처리했을 때 accept가 되는지를 True/False로 반환한다.

t=int(input())
for i in range(t):
    string=list(input())
    #print(string)
    state=1
    if check(string, state)==True:
        print("YES")
    else:
        print("NO")

 

string에서 앞 한글자씩 떼서 pop변수에 저장해주었다.

이 pop과 state 값을 이용해 transition을 해주었다.

한가지 주의할 점은 state5에서 1이 들어오면 두가지 경우로 나눠진다는 것이다.

def check(string,state):
    #print(string,state)
    while(1):
        if len(string)==0:
            if state==1 or state==5:
                return True
            else:
                return False
        else:
            pop=string[0]
            tempstring=string[1:]
            if pop=='0' and state==1:
                return check(tempstring,6)
            elif pop=='1' and state==1:
                return check(tempstring,2)
            elif pop=='0' and state==2:
                return check(tempstring,3)
            elif pop=='0' and state==3:
                return check(tempstring,4)
            elif pop=='0' and state==4:
                return check(tempstring,4)
            elif pop=='1' and state==4:
                return check(tempstring,5)
            elif pop=='0' and state==5:
                return check(tempstring,6)
            elif pop=='1' and state==5:
                if check(tempstring,5) or check(tempstring,2):
                    return True
                else:
                    return False
            elif pop=='1' and state==6:
                return check(tempstring,1)
            else:
                return False

 

그래프를 잘 그렸고 위에서 얘기한 두 가지 경우가 나오는 부분만 코딩을 잘 했다면 쉽게 할 수 있는 문제였다.