문제

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

소스코드

if __name__ == "__main__":
    s = list(input().rstrip())
    t = list(input().rstrip())
    flag = False

    def dfs(arr):
        global flag
        if len(arr) == len(s):
            if arr == s:
                flag =  True
            return 
        
        if arr[-1] == 'A':
            arr.pop()
            dfs(arr)
            arr.append('A')
        
        if arr[0] == 'B':
            arr.reverse()
            arr.pop()
            dfs(arr)
            arr.append('B')
            arr.reverse()


    dfs(t)

    print(1 if flag else 0)

설명

백트래킹을 이용해야하는 완전탐색 문제이다.
S -> T를 찾는것 보다 T -> S를 찾는 것이 훨씬 경우의 수가 줄어 들어 시간 초과를 면할 수 있다. 이건 여러 풀이가 있는 방법이 아니고 이렇게 푸는게 맞는 문제 같다;;;

백트래킹을 해줘야하기 때문에 무조건 원복을 시켜서 탐색을 해야한다. 내가 B를 탐색할 땐 어짜피 함수 끝나는데 왜 원복해줘야하지? 했는데 t를 매개변수로 넣었지만 리스트라 주소값이 전달되면서 arr가 변경되면 t도 변경된다

후기

처음엔 S -> T 변경되는 부분을 완전 탐색했는데 시간초과가 발생하였다. 그래서 dfs(s,0) 해줘서 첫번째에 A를 붙여서 첫번째 문자열 + A 문자열 이렇게 비교해서 아예 안되면 빼버려야지! 하고 if arr[:l+1] != t[:l+1]: return 이런 말도 안되는 조건문을 넣어서 함수를 탈출했는데 테케중에 하나가 s= 'A'였던거지 s가 10문자 이상이면 어쩔래ㅠ.ㅠ 쓸모 없고 잘못된 접근이었다. 좀 더 깊고 넓게 생각해보자