(Python) 백준 12904. A와 B

문제

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

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

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.
  주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.
  상세 설명

• 주어진 A를 B로 만들 수 있는지를 확인하는 문제이다.
• 처음에는 접근을 'A를 B로 만들기' 로 해서 시간초과가 발생했다.
• 반대로 'B'를 'A'로 만드는 방법은 하나이기 때문에, B를 변경해가면서 A가 될 수 있는지를 확인했다.
• 두 번째 연산의 경우에는 문자열을 뒤집는 연산이 추가되는데, 일일히 뒤집으면서 비교하면 시간복잡도 상 비효율적이기 때문에 뒤집힌지 확인하는 변수를 하나 선언하고, 그에 따라서 다른 연산을 하도록 설정하였다.
• popleft()를 사용하기 위해서 deque를 활용했다.

from collections import deque
A = input() # A값 받아오기.
B = deque(input()) # B값 받아오기. pop과 popleft를 사용할 예정이므로 deque로 만들기
reverse_flag = 0 # 뒤집혔는지 아닌지를 판별하는 변수 선언

while len(B)> len(A): # B의 길이가 A의 길이와 같아질 때까지 반복
    if reverse_flag: # 만약 뒤집혀있으면
        if B[0] == 'A': # 첫번째 변수를 확인함
            B.popleft()
        else:
            B.popleft()
            reverse_flag = 0
    else: # 만약 뒤집히지 않았으면
        if B[-1] == 'A': # 마지막 변수를 확인함
            B.pop()
        else:
            B.pop()
            reverse_flag = 1

res_B = ''.join(B) # 비교를 위해서 B를 문자열로 만듦
if reverse_flag: # 만약 뒤집혀있을 경우에는
    if res_B[::-1] == A: # B를 뒤집어서 비교
        print(1)
    else:
        print(0)
else:
    if res_B == A:
        print(1)
    else:
        print(0)

틀린 코드

• DFS를 사용해서 A가 B의 길이까지 할 수 있는 모든 연산을 수행하도록 설정
• 필요 없는 루트까지 전부 탐색하기 때문에 시간초과가 발생했음

  def DFS(A,B,f): # DFS를 이용해서 B로 변환할 수 있는지 확인
     if len(A) == len(B): # B의 길이와 같아진다면
         if f: # 만약 뒤집혀있다면
             if A[::-1] == B: # A를 뒤집어서 비교
                 print(1) # 성공한다면, 더이상 진행할 필요가 없으니 exit로 탈출
                 exit()
         else: # 아니라면
             if A == B: # A와 B를 비교
                 print(1)
                 exit()
         return
     
     if not f:
         DFS('B'+A, B, 1)
         DFS(A+'A',B,0)
     else:
         DFS(A+'B',B,0)
         DFS('A'+A,B,0)
  A = input()
  B = input()
  DFS(A,B,0)
  print(0) # DFS를 돌렸는데도 값이 나오지 않았으면 0을 프린트