문제 링크

풀이

S -> T로 만들며 비교하는 방법보다는 T -> S로 만드는 방법이 시간을 절약할 수 있을 거 같아서 그렇게 풀이하였다.
BFS를 사용해서 T가 "A"로 끝나는 경우에는 A를 제거 후 큐에 추가, "B"로 시작하는 경우에는 문자열을 뒤집은 후 B를 제거한 후에 큐에 추가해주었다.

"A"로 끝나고, "B"로 시작하는 경우를 동시에 만족할 수 도 있으니 else-if가 아닌 각각의 if문으로 나누어야한다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol12919 {
    static String S;
    static String T;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine();
        T = br.readLine();
        if (bfs()) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    public static boolean bfs() {
        Queue<String> q = new LinkedList<>();
        q.add(T);

        while (!q.isEmpty()) {
            String curr = q.poll();

            if (curr.length() < S.length()) {
                break;
            }

            if (curr.equals(S)) {
                return true;
            }

            if (curr.endsWith("A")) {
                q.add(removeA(curr));
            }
            if (curr.startsWith("B")) {
                q.add(reverseAndRemoveB(curr));
            }

        }
        return false;
    }

    public static String removeA(String origin) {
        StringBuilder sb = new StringBuilder(origin);
        return sb.deleteCharAt(origin.length() - 1).toString();
    }

    public static String reverseAndRemoveB(String origin) {
        StringBuilder sb = new StringBuilder(origin);
        return sb.reverse().deleteCharAt(origin.length() - 1).toString();
    }
}