[BOJ/C++] 12919: A와 B 2

🏅 Gold 5

✏️ 1차 솔루션

⭐️ 완전탐색

1. 둘 중 길이가 짧은 것을 바꾸기
2. 두 문자가 같아질 때까지 탐색
   1) 두 문자가 같으면 탐색 성공
   2) 짧은 문자에 A 추가한 것이 긴 문자에 포함되면 continue
   3) 짧은 문자에 B 추가하고 reverse 한 문자가 긴 문자에 포함되면 continue
   4) 이외의 경우는 존재하지 않는 문자열을 바꿀 수 없는 것이기 때문에 0

🚨 trouble

틀렸다고 뜸..완전탐색이라 비효율적인 방법인 것 같음

✏️ 최종 솔루션

⭐️ DFS
⭐️ 긴 문자에서 지워가며 짧은 글자를 만들 수 있는 지 탐색

1. 현재 문자와 짧은 문자가 같으면 true
2. 현재 문자가 짧은 문자보다 길이가 작거나 같으면 false
3. 현재 문자의 마지막 글자가 A 이면 마지막 글자 빼고 이어서 DFS
4. 3에서 DFS 결과가 false 이면 현재 문자 reverse
5. reverse 결과의 마지막 글자가 B 이면 마지막 글자 빼고 이어서 DFS
6. 이외의 경우 false

📌 self feedback

짧은 문자에서 긴 문자를 만들어 가면 A 를 붙이거나 B 를 붙이거나 두 경우를 무조건 수행해줘야하고 할 때마다 문자의 포함여부를 확인해줘야해서 시간복잡도가 늘어남
하지만, 긴 문자에서 지워가면 마지막 문자가 A 이고 첫번째 문자가 B 인경우에만 두 가지 경우를 모두 따져주고 그 마저도 A 를 뺐을 때 문자열을 바꿀 수 없는 경우에 한해 진행되기 때문에 복잡도를 줄일 수 있음

✏️ 최종 code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string s1,s2;
bool success=false;
bool dfs(string s) {

    if(s==s1) return true;
    if(s.size()<=s1.size()) return false;
    
    if(s.back()=='A') {
        s.pop_back();
        if(dfs(s)) return true;
        s.push_back('A');
    }
    
    reverse(s.begin(), s.end());
    if(s.back()=='B') {
        s.pop_back();
        return dfs(s);
    }

    return false;
}

int main() {
    string s,t;
    cin >> s>>t;
    
    // 둘 중 길이가 짧은 것을 바꾸기 s1 -> s2
    if(s.size()<t.size()) {
        s1=s;
        s2=t;
    }
    else if(s.size()>t.size()) {
        s1=t;
        s2=s;
    }
    else {
        cout << 0;
        return 0;
    }
    
    cout <<dfs(s2);
    
}