[12919] A와 B 2 - Python

문제 유형 : BFS / Brute-Force 

문제 요약 : A와B로 이루어진 문자열 S 에서 T로 바꿀 수 있으면 1, 바꿀 수 없으면 0을 출력하는 문제. 

---

전체 코드

import sys
input = sys.stdin.readline

s = input().strip()
t = input().strip()

def dfs(term):
    if term == s:
        print(1)
        sys.exit()
    elif len(term) == 0:
        return 0

    if term[-1] == 'A':
        dfs(term[:-1])
    if term[0] == 'B':
        dfs(term[1:][::-1])

result = dfs(t)
if result == None:
    print(0)

 

문제 해설

- 문제 그대로 s를 t로 바꾸려고 하면 수 많은 경우의 수가 너무 많다. 즉, brute-force로 풀 수 있지만, 좀 더 좋은 코드를 만들기 위해 다른 방식을 생각해야 한다. 

- 반대로 t를 s로 바꾼다. 맨 끝에 A가 있으면 A를 삭제하고, 맨 앞에 B가 있으면 B를 삭제하고 문자열을 뒤집는다.

- 재귀함수로 규칙을 적용하다가 s를 발견하면 1을 출력하고 종료한다.

 

Tip)

- 만약 재귀가 중간에서 끝나거나, 문자열이 다 없어진다면, None을 리턴한다. 

- Python 특성상 재귀함수를 return 할 때, return값이 없으면 값이 없는 채로 return되는게 아니라 None을 리턴한다.

 따라서, 해당 특성을 잘 이용하여 return문을 사용해야 한다.