백준 3300번 - 무어기계 파이썬(pypy3) 풀이

문제

무어 기계는 상태에 의해서 출력이 결정되는 유한 상태 기계이다. 무어 기계는 이름은 미국의 수학자이자 컴퓨터 과학자 Edward F. Moore의 이름을 따서 지었다. 무어 기계의 상태 전이는 입력에 의해서 정해진다. 예를 들어, 입력이 "aabba"이면, 아래와 같은 무어 기계의 출력은 "PRETTY"가 된다.

 

 

 

위의 그림에서 동그라미는 상태를 나타내고, 화살표 위의 글자는 입력 심볼을 나타낸다. 상태 중 하나는 시작 상태로 디자인 되어져 있다. 이 상태는 출발 노드가 없는 화살표로 나타나 있다. 이 경우에 시작 상태는 1번 상태이다. 상태 N과 출력 심볼 S는 N/S로 나타낸다.

 

대부분 경우에 무어 기계는 사이클을 가진다. 이 문제에서는 사이클이 전혀 없는 무어 기계를 다루며, 이런 종류의 기계를 직병렬 무어 기계라고 한다.

 

직병렬 무어 기계의 한 출력 심볼이 지워져 있다. 기계의 출력이 주어졌을 때, 지워진 심볼을 찾는 프로그램을 작성하시오. 항상 지워진 심볼을 찾을 수 있는 것은 아니다.

 

예를 들어, 아래 그림과 같은 직병렬 무어 기계가 있다.

 

 

 

위의 그림에는 상태를 간단하게 나타내기 위해 출력 심볼만 나타나 있다. 빈 원은 출력 심볼이 지워진 상태이다. 예를 들어, 기계의 출력이 "ADC"인 경우에는, 지워진 심볼이 D임을 알 수 있다. 하지만, 출력이 "ABC" 라면, 주어진 심볼을 유일하게 결정할 수 없다. "ABD"는 이 기계에서 나올 수 없는 출력이기 때문에, 불가능한 경우이다.

 

직병렬 무어 기계는 직병렬 그래프로 나타낼 수 있고, 간단히 표현할 수 있다. 상태가 하나이고, 출력이 S인 무어 기계는 'S' 로 나타낸다. 상태가 하나이고, 출력 심볼이 지워진 무어 기계는 '_'로 나타낸다. 여러 개의 부분 기계 M1, M2, ..., Mk가 직렬로 연결된 무어 기계는 M1M2...Mk로 나타낸다. 또, 부분 기계가 병렬로 연결된 무어 기계는 M1|M2|...|Mk로 나타낸다. 한 무어 기계가 더 큰 무어 기계의 일부로 사용된다면, 그 부분을 괄호로 감싼다. 이 방법을 사용하면, 위의 무어 기계는 A(B|_)C로 나타낼 수 있다.

 

직병렬 무어 기계와 그 기계의 출력이 주어졌을 때, 지워진 심볼을 구하는 프로그램을 작성하시오. 만약, 지워진 심볼을 유일하게 결정할 수 없다면, '_'를 출력한다. 또, 기계에서 나올 수 없는 출력이 주어진 경우에는 '!'를 출력한다.

 

 

문제유형

문자열

파싱

정규표현식

 

---

 

 골드 2의 문자열 파싱문제. 정규표현식을 사용하여 간단하게 풀이하였다. 입력 자체가 정규표현식의 문법으로 표현하기 좋게 들어온다. 골드 2의 난이도를 온몸으로 느끼기 위해서는 정규표현식을 사용하지 않고 풀이를 해야할듯하다. 이 문제는 입력으로 '_' 문자를 포함한 무어 기계와 출력이 입력되며, 입력된 출력으로 무어 기계의 '_' 문자를 구할 수 있는지를 알아내는 문제이다.

 

 

 위 입력 예시에서 무어 기계가 가질 수 있는 상태는 총 3가지(ABE, ACDEG, ACD_G)가 있다. 이때 '_' 값을 알아내기 위해서는 입력된 출력값이 'ACD[A-DF-Z]G'의 형태를 가져야 하며, 'ABE, ACDEG'와 같이 입력되면은 무어기계의 출력값은 맞지만 '_'값을 유일하게 식별할 수 없으므로 '_'를 출력해야한다. 이 두가지 상태를 합치면 'ACD[A-Z]G'라는 정규식을 얻을 수 있으며, 이 정규식에 매칭되지 않으면 무어기계의 출력이 아니므로 '!'를 출력하면 된다. 이때 아래와 같은 순서로 진행하면 'ACD[A-DF-Z]G'정규식을 생략하고 알고리즘을 작성할 수 있다.

 

 

1. 입력된 출력이 무어 기계에 포함되는지 확인 ( 아니라면 ! 출력 )
2. 입력된 출력이 '_'가 포함된 루트를 거치는지 확인 ( 아니라면 _ 출력 )
3. 만약 '_'가 포함된 루트의 출력이라면 _의 위치에 해당하는 문자가 무엇인지 확인 ( 해당 알파벳 출력 )

 

 

 여기서 다음과 같은 테스트케이스를 통과하기 위해 정규식에 첫번째와 마지막 위치에 ^, $ 키워드를 추가하였다. 만약 이 키워드가 없다면 입력이 모두 동일한 테스트케이스를 통과할 수 없다. (아래 예제에서 print()문 옆의 주석은 출력을 의미한다)

 

tc = re.match("AAAAA", "AAAAAA")
print(tc1) # <re.Match object; span=(0, 5), match='AAAAA'>
tc = re.match("^AAAAA$", "AAAAAA")
print(tc1) # None

 

 

 전체 코드를 작성하면 다음과 같다.

 

import re

# main
for i in range(int(input())):
    inVal = input()
    inVal2 = input()

    # if go _
    patternA = "^" + re.sub("_", "[A-Z]+", inVal) +"$"
    # if don't go _
    patternB = "^" + re.sub("_", "", inVal) +"$"
    mA = re.match(patternA, inVal2)
    mB = re.match(patternB, inVal2)

    if not mA:
        print("!")
    elif mB:
        print("_")
    else:
        for i in range(26):
            c = chr(ord('A')+i)
            patternRST = "^" + re.sub("_", c, inVal) +"$"
            if re.match(patternRST, inVal2):
                print(c)

 

 

3300번: 무어 기계