[BOJ_12904/Python] A와 B

문제

12904번: A와 B

12904번: A와 B

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

---

풀이

백트래킹으로 푸는 문제라고 생각했다. 그런데 노드의 유망성을 잘 검사했다고 생각했는데도 시간초과가 발생했다.

import sys
sys.setrecursionlimit(10**6)

def recursion(s):
    if len(s) > len(T):
        return

    if s == T:
        print(1)
        exit(0)

    if s in T or s[::-1] in T:
        recursion(s + "A")
        recursion(s[::-1] + "B")

# 입력
S = input().strip()
T = input().strip()

# 풀이
recursion(S)

# 출력
print(0)

개선한 풀이

S에서 T를 만드는게 아니라 T에서 S를 만들어야겠다고 생각했다.

트리구조를 직접 그려본 결과 S에서 T를 만드는 과정에서는 많은 노드를 탐색하는 반면, T에서 S를 만드는 과정은 정답루트만 존재한다는 것을 발견했다.

완성된 코드는 다음과 같다.

# 입력
S = input().strip()
T = input().strip()

# 풀이
while True:
    if len(T) <= len(S):
        break

    if T[-1] == 'A':
        T = T[:-1]
    else:
        T = T[:-1]
        T = T[::-1]

# 출력
print(1 if S == T else 0)