주어진 상태로부터 특정한 연산을 통해 목표 상태로 도달하는 문제에서 반대로 생각하여 목표 상태에서 역연산을 통해 시작 상태로 도달하게 한다면 경우의 수를 많이 줄일 수 있다. 이 문제 또한 반대로 생각하는 아이디어가 가장 중요한 문제였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static Queue<StringBuilder> q;
static String S, T;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
S = br.readLine();
T = br.readLine();
q = new LinkedList<>();
StringBuilder sb = new StringBuilder(T);
if(bfs(sb)) System.out.println(1);
else System.out.println(0);
}
private static boolean bfs(StringBuilder sb) {
q.offer(sb);
while(!q.isEmpty()) {
StringBuilder now = q.poll();
if(now.toString().equals(S)) {
return true;
}
// 목표 문자열의 길이보다 커야한다.
if(now.length() > S.length()) {
StringBuilder next = null;
// 뒤에서 A를 제거하기
if(now.charAt(now.length() - 1) == 'A') {
next = new StringBuilder(now.substring(0, now.length() - 1));
q.offer(next);
}
// 뒤에서 B를 제거하고 뒤집기
if(now.charAt(now.length() - 1) == 'B') {
next = new StringBuilder(now.subSequence(0, now.length() - 1));
next.reverse();
q.offer(next);
}
}
}
return false;
}
}