백준 12919 - A와 B 2

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, S와 T 두 문자열이 주어지면 S를 T로 바꿀 수 있는지 여부를 출력해야 한다.

S를 T로 바꾸는 연산은 두 가지가 존재한다.

• 문자열 맨 끝에 'A'를 추가한다.
• 문자열 맨 끝에 'B'를 추가한 뒤 문자열을 뒤집는다.

 

해당 문제는 BFS로 해결할 수 있다.

단, 한 가지 트릭이 존재한다.

우선, 가장 기본적인 접근법부터 살펴 보자.

S에서 T로 만들기 위해서는 결국 A를 추가하거나 B를 추가한 뒤 뒤집거나 둘 중 하나를 선택하여 문자열을 만들어 나가야 한다.

그러한 과정에서 생기는 중간 단계의 문자열이 존재할 것이다.

따라서, 중간 단계의 문자열을 만들었는지 아닌지를 확인하여 BFS를 진행하면 될 것이다.

 

이렇게 진행해도 S를 T로 만들 수 있는지 없는지는 확인할 수 있다.

하지만, 시간 초과로 인해 문제는 실패할 것이다.

S를 T로 만드는 경우의 수가 너무 많기 때문이다.

다른 말로는 가능성이 없는 분기까지 포함하여 BFS를 진행할 것이다.

 

이를 해결하기 위해서는 반대로 생각하면 된다.

즉, T에서 S로 문자를 제거해 나가면 된다.

제거나 추가나 똑같다고 생각이 들 수 있다.

하지만, 자세히 생각해 보면 엄연히 다르다는 것을 알 수 있다.

예를 들어, A에서 BAA를 만든다고 생각을 해보자.

A에서 BAA를 만든다고 하면 문자열이 어떻게 바뀔지 추가하는 순간에 예상할 수 없으므로 모든 문자열을 만들어보며 BFS가 진행된다.

즉, BAA가 될 수 없는 BAB, AAA 등 불필요한 문자열들이 포함된 채 BFS를 진행할 것이다.

지금은 문자 2개만 추가하면 되기 때문에 상관없어 보이지만 문제의 상한이 최대 50이기 때문에 $2^50$개의 문자열을 비교해야 할 상황이 올 수 있다.

반면, BAA를 A로 만드는 과정에서는 분기 내에 필요 없는 문자열이 존재할 수 없다.

만약 A를 만들 수 없는 문자열들이 존재하다는 것은 A에서 BAA를 만들 수 없다는 뜻과 같기 때문이다.

따라서, T에서 S를 만드는 분기가 훨씬 적다.

 

정리하자면, T에서 시작하여 맨 끝이 A라면 A를 제거한 문자열을 만들어 BFS를 진행하고 맨 앞이 B라면 문자열을 뒤집은 뒤 맨 끝을 제거한 문자열을 만들어 BFS를 진행하면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

string S, T;

void reverse(string& str)
{
    string result;

    for (int i = str.length() - 1; i >= 0; i--)
    {
        result += str[i];
    }

    str = move(result);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> S >> T;

    set<string> checked;
    queue<string> q;

    q.push(T);
    checked.insert(T);

    while (!q.empty())
    {
        auto current = q.front();
        q.pop();

        if (current.length() < S.length()) break;

        if (current.back() == 'A')
        {
            string newStr = current;
            newStr.erase(newStr.length() - 1);

            if (newStr == S)
            {
                cout << 1;
                return 0;
            }

            if (checked.count(newStr) == 0)
            {
                checked.insert(newStr);
                q.push(newStr);
            }
        }
        
        if(current[0] == 'B')
        {
            string newStr = current;
            reverse(newStr);
            newStr.erase(newStr.length() - 1);

            if (newStr == S)
            {
                cout << 1;
                return 0;
            }

            if (checked.count(newStr) == 0)
            {
                checked.insert(newStr);
                q.push(newStr);
            }
        }
    }

    cout << 0;


    return 0;
}

---