BOJ 12919 A와 B 2

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

문제

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

---

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

---

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

---

예제 입력 1

A
BABA

예제 출력 1

1

예제 입력 2

BAAAAABAA
BAABAAAAAB

예제 출력 2

1

… 이하 예제 생략

---

코드

처음 시도에서는 문자열 S에서 위 설명에 나온 두 가지 연산을 해 가며 T와 비교했었다. 물론, 최악의 경우 $2^{49}$가지의 연산을 해야 하기 때문에 A와 B의 등장횟수를 체크해가며 가능한 경우를 비교해갔다.

하지만, 시간 초과가 발생했고 좀 더 효율적인 방법을 생각해봤다.

문자열 T를 봤을 때, 맨 뒤에 문자 A가 있다는 것은 첫 번째 연산을 했던 것이다. 반대로 맨 앞에 문자 B가 있다는 것은 두 번째 연산을 했던 것이다.

즉, 문자열 T에서 문자를 제거하며 문자열 S와 비교하는 것은 문자의 등장 횟수 뿐만 아니라 문자들이 배열된 위치까지 고려하는 방식이기 때문에 처음 시도했던 문자의 등장횟수를 체크하며 문자열을 비교했던 경우보다 훨씬 적은 경우를 비교해보는 것이었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static String S;
    static boolean isPossible = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine();
        String T = br.readLine();

        dfs(T);

        System.out.println(isPossible ? 1 : 0);
    }

    static void dfs(String t) {
       if(t.length() == S.length()) {
           if(t.compareTo(S) == 0) {
               isPossible = true;
           }

           return;
       }

        /**
         * t의 맨 앞이 B일 경우, 맨 앞의 B를 제거하고 뒤집어서 탐색 진행
         * 즉, 두 번째 연산을 UNDO 하며 탐색하는 것을 의미
         */
       if(t.charAt(0) == 'B') {
           StringBuilder newT = new StringBuilder(t);
           newT.deleteCharAt(0);
           newT.reverse();
           dfs(newT.toString());
       }

        /**
         * t의 맨 뒤가 A일 경우, 맨 뒤의 A를 제거하고 탐색 진행
         * 즉, 첫 번째 연산을 UNDO 하며 탐색하는 것을 의미
         */
       if(t.charAt(t.length() - 1) == 'A') {
           dfs(t.substring(0, t.length() - 1));
       }
    }
}