16492번 - 패턴 코드 진위

가방 제조업체 부비통에서는 제품의 진품여부를 추후에 확인할 수 있도록, 출시되는 백의 배경에 비밀스런 패턴 코드를 심어놓는다. 이 패턴 코드는 다음과 같이 여러 개가 자동으로 생성되고, 제품마다 무작위로 심어지게 된다. 패턴 코드 생성기는 세 가지로 구성된다. 패턴 코드에 사용되는 심볼의 집합, 시작 심볼, 유한개의 규칙들이다.

규칙은 두 종류가 있다. 생성 규칙과 소멸 규칙. 생성 규칙은 심볼 하나가 어떤 다른 심볼 문자열로 변환되는지 정한 규칙이다. 소멸 규칙은 소멸 되는 심볼 문자열이 모여 있다.

예를 들어, 심볼의 집합이 {A, B} 이고, 시작 심볼은 A이며, 생성 규칙은 A → AB, B → A, 소멸 규칙은 AA라고 하자.

그러면, A에서 시작해서 매 단계마다 “모든 생성(→)후 모든 소멸(↘)”을 적용하면서 (생성 규칙을 모두 적용하고 그 결과에 소멸 규칙을 모두 적용하면서) 다음과 같은 패턴 코드가 계속 생성된다:

A → AB  ↘ AB → ABA  ↘ ABA → ABAAB  ↘ ABB → ABAA  ↘ AB →  · · ·

즉, A에서 시작해서 네 번째 생성-후-소멸 결과의 패턴 코드는 ABB가 된다.

소멸 규칙은 주어진 문자열에서 최대로 소멸 시킬 수 있을 만큼 소멸시키게 된다. 없앨 수 있는 부분문자열이 겹치더라도 모두 적용된다. 예를 들어 현재 문자열이 AAABA 라면, 소멸될 수 있는 부분 문자열(AA)가 두 개 앞쪽에 겹쳐 있지만(AAA) 모두 적용되어 소멸되고 뒤에 오는 BA만 생성 규칙에 의해 AAB가 된다.

주어진 룰에서 특정 코드가 만들어 질 수 있는 패턴 코드인지 판별하는 프로그램을 작성하라. 단, 생성 및 소멸 규칙이 10번 적용되었는데도 대상 코드가 나오지 않으면, 패턴 코드가 아니라고 판단한다. 심볼은 A, B 이고, 시작 심볼은 항상 A이다.

한 단계는 생성 규칙과 소멸 규칙을 순서대로 모두 적용해야 한다. 한 단계에서 생성 규칙만 사용해서 만든 패턴 코드(아직 소멸 규칙을 적용하지 않은 코드)가 중간 계산을 하기 위해 임시로 만든 패턴 코드이다.

생성 규칙, 소멸 규칙, 판정하고 싶은 패턴이 한 줄에 하나씩 주어지고, 다음과 같은 형식이다.

• 생성 규칙 X → Y: gen: X -> Y
  • X는 심볼 하나, Y는 길이가 1이상 3이하인 심볼 문자열
• 소멸 규칙 X: del: X
  • X는 길이가 2이상 5이하인 심볼 문자열
• 판정하고 싶은 패턴: target: X
  • X는 길이가 2이상 20이하인 심볼 문자열

생성 규칙, 소멸 규칙은 1개 또는 2개가 주어지며, 판정하고 싶은 패턴은 항상 1개만 주어진다. 또, 생성 규칙이 모두 주어진 후 소멸 규칙이 주어지고, 소멸 규칙이 주어지고난 후 판정하고 싶은 패턴이 주어진다.

하나의 심볼이 두 번 이상 생성 규칙으로 주어지는 경우는 없다.

판정하고 싶은 패턴을 만들 수 있는 경우 O, 없는 경우 X를 출력한다.