백준 12904 - A와 B

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 두 개의 문자여 S, T가 주어졌을 때 S에서 T로 변환할 수 있는지 여부를 출력하는 문제이다.

단, S에서 T로 변환하는 연산은 두 가지이다.

• 제일 뒤에 A 추가하기
• 문자열을 뒤집고 B 추가하기

 

해당 문제는 S에서 T로 변환하여도 성공하는지 알 수 없지만, S에서 T로의 변환보다 T에서 S로의 변환이 훨씬 효율적이라는 것은 알 수 있다.

그러한 이유는 S에서 T로 변환하게 되면 문자열을 뒤집는 연산때문에 올바르게 진행되는지 아닌지 판단할 수 없다.

하지만, 반대의 경우에는 올바르지 않은 진행을 바로 찾아내 진행하지 않을 수 있다.

 

예를 들어, 'B'(S)에서 'ABBA'(T)로 변환한다고 가정해 보자.

그렇다면, B에 A를 추가하거나 뒤집어 B를 추가하면 'BA', 'BB'가 된다.

여기에 똑같이 진행하면 'BAA', 'ABB', 'BBA', 'BBB'가 된다.

여기서 'BAA'와 'BBB'는 절대고 'ABBA'가 될 수 없다.

하지만 이를 판단하기는 쉽지 않다.

길이로 확인하기도 애매하고 앞에서부터 한글자씩 비교하기도 쉽지 않다.

하지만, 'ABBA'에서 'B'로 연산을 거꾸로 적용시킨다고 생각해 보자.

'ABBA'에서 제일 끝이 A이면 첫 번째 연산만 B라면 두 번째 연산만 적용시킬 수 있다.

따라서, 제일 끝 글자를 보고 어떠한 연산을 적용시킬지 결정하면 된다.

//Add A
{
    auto temp = str;
    if (temp.back() == 'A')
    {
        temp.pop_back();
        if (checked.count(temp) == 0)
        {
            q.push(temp);
            checked.insert(temp);
        }
    }
}

//reverse + B
{
    auto temp = str;
    if (temp.back() == 'B')
    {
        temp.pop_back();
        reverse(temp.begin(), temp.end());
        if (checked.count(temp) == 0)
        {
            q.push(temp);
            checked.insert(temp);
        }
    }
}

이렇게 진행하다 문자열이 S와 일치하는 순간 1을 출력하고 종료하면 된다.

하지만 큐가 빌때까지 진행해도 S를 찾지 못하면 변환할 수 없는 문자열이기 때문에 0을 출력하면 된다.

---

 

 

 

 

 

전체 코드

#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 <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

string S, T;


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

    cin >> S >> T;

    queue<string> q;
    set<string> checked;
    q.push(T);
    checked.insert(T);

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

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

        //Add A
        {
            auto temp = str;
            if (temp.back() == 'A')
            {
                temp.pop_back();
                if (checked.count(temp) == 0)
                {
                    q.push(temp);
                    checked.insert(temp);
                }
            }
        }

        //reverse + B
        {
            auto temp = str;
            if (temp.back() == 'B')
            {
                temp.pop_back();
                reverse(temp.begin(), temp.end());
                if (checked.count(temp) == 0)
                {
                    q.push(temp);
                    checked.insert(temp);
                }
            }
        }
    }

    cout << 0;

    return 0;
}

---