[ 백준 12919 ] A와 B 2 (C++) - DFS

---

🔗 문제 링크

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

12919번: A와 B 2

---

💡 문제 풀이 및 해석

1. 주어진 조건이 뒤에 'A'를 붙이는 것과 'B'를 붙이고 뒤집는 것이다.
2. 최악의 조건을 생각해보자. S.size() = 1, T.size() = 50 이다.
3. 여기서 S -> T 로 갈 때, 브루트포스하게 할 수 없다. 2의 50제곱은 좀 많이 크다.
4. S -> T 로 갈 때, 조건을 설정해주면 어떨까?? 이 문제는 사실 해답을 찾기 어려워 보인다. 만들 수 있는 방식이 1가지가 아닐 수 있기 때문이다.
5. 그럼 반대로 T -> S 는 어떨까? 조건이 반대로 주어질 때, 맨 뒤가 'A' 이거나 맨 앞이 'B'가 아닌 AxxB, BxxB 같은 형식들이 모두 걸러질 것이다.
6. 브루트포스이지만, 경우의 수가 절반으로 줄어든다. 그럼 최악의 경우 2의 25제곱인데, 이는 주어진 3200만 횟수이므로 2초가 아닌 0.5초에도 가능하다.

---

⭐️ 정답 코드 및 설명

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

using namespace std;

bool isAnswer = false;

string remove(string temp_s) {
    temp_s.pop_back();
    return temp_s;
}

string re(string temp_s) {
    reverse(temp_s.begin(), temp_s.end());
    temp_s.pop_back();
    return temp_s;
}

void sol(string S, string T) {

    if (T.size() == S.size()) {
        if (T == S) isAnswer = true;
        return;
    }
    while (T.size() > S.size()) {
        if (T[T.size() - 1] == 'A') {
            T = remove(T);
            sol(S, T);
            T += 'A';
        }

        if (T[0] == 'B') {
            T = re(T);
            sol(S, T);
        }
        return;
    }
}

void input(string& S, string& T) {
    cin >> S >> T;
}

int main() {

    string S, T;
    input(S, T);
    sol(S, T);
    if (isAnswer) cout << 1;
    else cout << 0;

    return 0;
}

---

🤔 문제 후기

처음에는 겹치는 단어들을 모두 삭제하면서 쌓아 올라가면 될 줄 알았는데, 생각해보니 시간이 너무 걸려서 조건을 찾아야 하나 생각했다. 하지만, 조건을 찾는 것은 너무 어려울 것 같았다. (솔직히 골드5라는 난이도를 봐서 더 이렇게 생각한 것 같다.) 그래서 반대로 탑다운 형식으로 하면 어떨까 생각하다가 풀게 되었다.