백준: 12919 A와 B 2

문제

12919번: A와 B 2

 

문제 풀이

 앞서 다룬 A와 B의 경우 항상 문자열 뒤에 A나 B가 추가 되어, 뒤에 어떤 문자가 오는지에 따라 처리하야 T를 S로 만들었다. 하지만 이 문제의 경우, 다른 조건이 주어짐으로써 맨 앞에 B이거나, 맨 뒤가 A인가를 판단하여 S를 만들기 위해 현재 상태에서 2가지로 가지를 뻣어 갈 수 있다. 따라서 A와 B를 푼 로직에서, `DFS를 통해 가지를 뻣어가며 백트랙킹`을 하게 되면 문제의 답을 찾을 수 있다.

 

코드

from sys import stdin


def dfs(string):
    if len(string) == len(s):
        if string == s:
            print(1)
            exit(0)
        return

    if string[0] == 'B':
        string = string[::-1]
        string.pop()
        dfs(string)
        # 백트랙킹을 위한 초기화.
        string.append('B')
        string = string[::-1]

    if string[-1] == 'A':
        string.pop()
        dfs(string)
        # 백트랙킹을 위한 초기화.
        string.append('A')


if __name__ == "__main__":
    s, t = [list(stdin.readline().strip()) for _ in range(2)]
    dfs(t)
    print(0)