[백준 12919] A와 B 2 (python)

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

12919번: A와 B 2

A와 B 2 문제

조건에 맞게 A를 추가하고 B를 추가하고 뒤집는 형식으로 만들 수 있는지 체크하는 문제

재귀를 활용하여 해결할 수 있었다.

📌문제 접근 포인트

1. 요구 조건대로 하나씩 늘려가면서 탐색하는 방법도 있겠지만, 반대로 T를 S로 만드는 게 더 간단하겠다 싶어서 T를 S로 만드는 방향으로 접근했다.
2. 조건에 만족하는 것을 찾아가기 위해 조건을 따져봤다.
문자의 시작 알파벳이 A일 경우 맨 뒤에 마지막 문자는 A만 나올 수 있다.
시작이 B면 맨 마지막 문자가 A와 B 둘다 나올 수 있다.
즉 마지막 알파벳이 A인 경우는 둘다둘 다 나올 수 있단 점과, 시작이 B인 경우에 A와 B 둘 다 나올 수 있단 점에서 마지막문자가 A일 때와 시작 문자가 B일 때로 조건을 나누면 다른 것은 따지지 않아도 되기에 이렇게 나누어 주었다.
3. 백트래킹을 구현하듯이 재귀로 코드를 작성하면 어렵지 않게 해결 할 수 있다.

⚙️ 내가 푼 정답 코드

def check(s):
    global result
    if len(s) == len(S): # 길이가 같고
        if s == S: # 모양 같으면
            result = 1 
            return # 끝
        return 
    if s[-1] == 'A': # 끝자리가 A면
        s.pop() # 빼보고
        check(s) # 다시 탐색
        s.append('A') # 아니었다면 다시 복구
    if s[0] == 'B': # 앞자리가 B면 
        s.reverse() # 뒤집어서
        s.pop() # 꺼내고
        check(s) # 다시 탐색
        s.append('B')
        s.reverse()
    
import sys
S = list(sys.stdin.readline().strip())
T = list(sys.stdin.readline().strip())
result = 0
check(T)
print(result)