[백준 C++] 12919 A와 B 2

문제

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

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

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.
  주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

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

풀이

S로부터 T가 되도록 문자를 이어붙여나가면 시간초과가 뜨는 문제이다.
항상 문제풀때 시간복잡도를 어림잡아 계산하며 풀어야한다.

역으로 T에서 S가 되도록 string에서 문자를 하나씪 줄여나가며 큐에 넣는 bfs방법으로 문제를 풀면 같은 길이의 string부터 꺼내서 확인하게된다.
(dfs 방법의경우는 스택에서 꺼낸 문자열에서 문자를 하나씩 지워나가는 방향으로 확인..)
어느 방법으로 풀든 주어진 시간내에 풀 수 있다.

어느정도 bfs dfs를 이해하고, 시간복잡도를 고려하여 거꾸로 접근할 생각을 했다면 쉽게 풀릴문제 이다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
using std::sort;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;

string S, T;
int S_size, T_size;
queue<string> list;
bool find = false;

void init();
void func();
string reverse(string s);
void init() {
    char s[51], t[51];
    scanf("%s%s", &s, &t);
    S = s; T = t;
    S_size = S.length(); T_size = T.length();
    list.push(T);
}

void func() {
    while (!list.empty()) {
        string str = list.front();
        int len = str.length();
        list.pop();
        if (len == S_size) {
            if (str.compare(S) == 0) {
                printf("1");
                find = true;
                return;
            }
        }
        else {
            if (str[len - 1] == 'A') { //1. 맨끝이 A라면
                string _ = str.substr(0, len - 1); //끝의 A제거
                list.push(_); //제거후 큐에 넣는다.
            }
            if (str[0] == 'B') { //2. 뒤집었을때 맨끝이 B라면
                string _ = reverse(str).substr(0, len - 1);
                list.push(_);
            }
        }
    }
    if (!find) printf("0");
}

string reverse(string s) {
    for (int i = 0; i < s.length() / 2; i++) {
        char _ = s[i];
        s[i] = s[s.length() - i - 1];
        s[s.length() - i - 1] = _;
    }

    return s;
}

int main(void) {
    init();
    func();


    return 0;
}