[골드 5] 백준 12919 - A와 B 2 (파이썬)

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

풀이

• 문자열 S에서 시작하여 문자열 T를 만들 수 있는지 판단하는 문제이다.
• 수행할 수 있는 연산은 다음과 같다,
  1. 문자열 뒤에 ‘A’ 추가
  2. 문자열을 뒤집고 뒤에 ‘B’ 추가

하지만 이 코드에서는 역방향으로, 즉 T에서 시작해서 S로 갈 수 있는지 확인한다.

def dfs(t):
    if len(t) == len(S):
        return t == S

현재 문자열 t의 길이가 S와 같아졌다면 t == S 인지 비교해서 결과를 반환한다.

if t[-1] == "A":
    if dfs(t[:-1]):
        return True

재귀 조건으로 문자열 끝이 A라면 A를 추가한 결과였을 수 있으므로 마지막 문자를 제거하고 재귀를 호출한다.

if t[0] == 'B':
    if dfs(t[1:][::-1]):
        return True

문자열 시작이 B라면 B를 뒤에 붙이고 뒤집은 결과였을 수 있으므로, 첫문자를 제거하고, 뒤집고, 재귀를 호출한다.

시간 복잡도 분석

• 최악의 경우 문자열 길이가 최대 50이므로
• 재귀 깊이는 최대 50이며
• 가지치기가 잘 작동하면 효율적이다.

코드

# 백준 12919 - A와 B 2
# 분류 : 문자열
 
S = input()
T = input()
 
def dfs(t) :
    if len(t) == len(S) :
        return t == S
    
    if t[-1] == "A" :
        if dfs(t[:-1]) :
            return True
    
    if t[0] == 'B' :
        if dfs(t[1:][::-1]) :
            return True
 
    return False
 
if dfs(T) :
    print(1)
else :
    print(0)