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

1. 코드

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

S -> T 로 접근하지 않고
T -> S 를 만드는 방향으로 접근한다.
"""
def dfs(string):
	# string == s 로 체크하면 string 의 길이가 0이 되는 순간 인덱스 에러가 발생
    # if len(string) == len(s):
        # return string == s

    if string == s:
        return True

    if len(string) > 1 and string[0] == 'B' and dfs((string[1:])[::-1]):
        return True

    if len(string) > 1 and string[-1] == 'A' and dfs(string[:-1]):
        return True

    # 파이썬은 자동으로 None 을 리턴한다.
    return False


s = input()
t = input()
if dfs(t):
    print(1)
else:
    print(0)

2. 후기

T에서 S를 만드는 방향으로 DFS함수를 작성하면 쉽게 풀린다.
주석처리한 if len(string) == len(s) 부분을 사용하지 않고 len(string) > 1 조건을 추가해서 풀어봤다.