[코딩테스트] 백준 A 와 B 2 파이썬(Python)

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

12919번: A와 B 2

S = list(input())
T = list(input())
def backtracking(now):
  global flag
  if now == S:
    flag = True

  if len(now) > 1:
    if now[-1] =='A':
      backtracking(now[:-1])
    if now[0] == 'B':
      backtracking(now[::-1][:-1])

flag = False  
backtracking(T)
if flag:
  print(1)
else:
  print(0)

S에서 T를 만드는 것이 아니라 T에서 S를 찾아가는 방식으로 문제를 해결하였습니다.

T에서 S를 찾아갈 때 backtracking함수를 작성하여 사용하였습니다.

 

다음은 backtracking 코드 내부를 확인해보겠습니다.

 

global flag로 함수 외부에 있는 flag변수를 제어하도록 하였습니다.

현재 문자 now가 S와 동일하다면 flag를 True로 변경해줍니다.

 

그리고 now의 길이가 1보다 작다면 error가 나오기 때문에 now의 길이가 1보다 클 때 라는 조건을 걸어줍니다.아래의 두 조건에 따라 backtrackng() 재귀적으로 호출합니다.

• 현재 문자 now의 마지막 단어[-1]가 A 일때 : now[:-1]로 A이전의 문자를 함수로 전달합니다.
  • now가 BABA라면 BAB를 전달
• 현재 문자 now의 첫 단어 [0]가 B일때 : now[::-1]로 뒤집어 주고 마지막 문자 이전의 문자까지 함수로 전달합니다.
  • now가 BAA라면 AA를 전달

함수가 종료가 되면 flag에 따라서 알맞은 값을 출력합니다.