백준 12919 A와 B 2

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

브루트 포스적으로 해결하는 문제.
연산에는 2종류가 있는데 각각의 경우의 수 마다 2개의 연산을 실행하면 연산량이 너무 많아져 할 수 없다.

호출을 줄이기 위해 뒤집은 문자열이나 원래 문자열의 substring이 아니라면, 해당 문자열 이후로는 가지치기를 멈췄다.

다른 사람들의 풀이를 보니, S -> T로 가는게 아니라 T -> S로 백트래킹을 써서 문제를 해결했다.

1) 파이썬 코드

s = list(input())
t = list(input())
t = ''.join(t)
reversed_t = t[::-1]
ans = 0
def check(string):
    if string in t or string in reversed_t:
        return True
    else:
        return False

def solve(k):
    global ans
    if len(k) == len(t):
        if k == t:
            ans = 1
        return
    temp = k
    temp += 'A'
    if check(temp):
        solve(temp)
    temp = k
    temp += 'B'
    temp = temp[::-1]
    if check(temp):
        solve(temp)

solve(''.join(s))
print(ans)

2) 자바 코드

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

public class Main {
    private static String S;
    private static int ans = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        S = br.readLine();
        String T = br.readLine();
        dfs(T);
        System.out.println(ans);
    }

    static void dfs(String string){
        if (S.length() == string.length()) {
            if (S.equals(string)){
                ans = 1;
                return;
            }
            return;
        }
        if (string.charAt(string.length() - 1) == 'A') {
            String substr = string.substring(0, string.length() - 1);
            dfs(substr);
        }
        if (string.charAt(0) == 'B') {
            String substr = string.substring(1, string.length());
            StringBuffer sb = new StringBuffer(substr);
            String reversed = sb.reverse().toString();
            dfs(reversed);
        }
        return;
    }
}