백준 12919번 A와 B 2

🔒[문제 url]

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

🔑알고리즘

$S$에서 두 가지 연산을 반복하며 $T$를 만들 경우 $O(2^s)$의 시간복잡도를 가지게 되어 시간초과 처리된다.
따라서 다음 두 조건을 만족하는 경우에 연산을 역으로 적용하며 BFS를 통해 $T$에서 $S$를 만든다.
1. 끝자리가 A인 경우 : 문자열 맨 뒤의 A를 제거한다.
2. 맨 앞자리가 B인 경우 : 문자열을 뒤집은 후 맨 뒤의 B를 제거한다.
이때, 두 연산의 결과가 동일하다면 하나의 문자열만 push 해주어야한다.

위 조건에 따라 BFS를 진행하다가 $S$와 같아진 경우에 1 출력 후 종료한다.

🐾부분 코드

생략한다.

🪄전체 코드

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

string s,t;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> s >> t;
}

void BFS()
{
    queue<string> q;
    q.push(t);

    while(!q.empty())
    {
        string now = q.front();
        q.pop();

        string next1,next2;

        // 뒤에 A 제거
        next1 = now;
        if(next1[next1.length()-1] == 'A')
        {
            next1.pop_back();
            if(next1 == s) { cout << 1; exit(0); }//종료 조건
            q.push(next1);
        }

        // 뒤집은 후 뒤에 B 제거
        next2 = now;
        if(next2[0] == 'B')
        {
            reverse(next2.begin(),next2.end());
            next2.pop_back();
        }
        else continue;

        if(next2 == s) { cout << 1; exit(0); }//종료 조건
        if(next1 == next2) continue;//연산 결과가 동일하다면
        else q.push(next2);//연산 결과가 다르다면 push
    }
}


void SOLVE()
{
    BFS();
    cout << 0;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

아무 생각없이 정방향으로 적용했다가 시초 뚜드려맞은 문제..ㅋㅋㅋㅋ
Gold5보다 Silver1이 더 긴장되는 거 나만 그래..?