백준 12919 A와 B 2

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

12919번: A와 B 2

---

문제

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

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

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

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

---

입력

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

---

DFS를 사용하였다..

처음에 S에서 시작해서 1) A를 추가하고 2) B를 추가하고 문자열을 뒤집는 방식으로 DFS를 했는데 가지 수가 너무 많아진다.

2^50...

 

그래서 T에서 역으로 S로 가는 방식으로 DFS를 적용하였다.

일단 문자열 T를 대상으로 DFS를 실행하는데, 예를 들어서 S가 A이고, T가 BABA인 경우를 생각해보자.

A
BABA

일단 문자열 S인 A에서 나올 수 있는 경우는

1) 문자열 뒤에 A를 추가하는 경우 , AA

2) 문자열 뒤에 B를 추가하고, 문자열을 뒤집는 경우이다.

 

T의 입장에서 보자면, 1)의 경우에는 문자열 끝에 A를 추가하니깐 문자열 끝이 무조건 A이다.

즉 T의 문자열 끝 문자가 A라면, 문자열 A를 더한 경우라고 판단 할 수 있다.

 

-> 이 경우 T의 문자열 끝 부분을 지워주고 DFS를 실행한다.

 

T의 입장에서 2의 경우, 문자열의 뒤에 B를 추가하고 문자열을 뒤집는 경우를 살펴보자.

A에서 뒤에 B를 추가하고 뒤집으면 AB->BA이다.

 

2)의 경우에는 첫부분이 무조건 B이다.

즉 T의 문자열 처음 문자가 B라면, 문자열뒤에 B를 더하고 뒤집은 경우라고 판단 할 수 있다.

 

->이경우 T의 문자열을 뒤집어주고 BA->AB, 문자열의 끝 문자 B를 제거해주고 DFS를 실행한다 (AB->A)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;
string s;
string t;

bool check = false;
void dfs(string str){

    /*기저 조건  */
    if(str == s){ 
        check = true;
        return;
    }
    if(s.size() > str.size()){
        return; 
    }
   
   /*1의경우 끝문자 지워주고 DFS */
    if(str[str.size()-1] == 'A'){
        string temp = str;
        temp.erase(temp.size()-1);
        dfs(temp);
    }
    
    /*2의 경우 문자열 뒤집어주고 끝문자 지워주고 DFS */
    if(str[0] == 'B'){
        string temp = str;
        
        reverse(temp.begin(),temp.end());
        temp.erase(temp.size()-1);
        dfs(temp);
    }

}
int main(void){
    cin >> s >> t;
    dfs(t);
    if(check == true){
        cout << 1;
        return 0;
    }
    cout << 0;
    return 0;
}