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

 
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
 
// 1. A 추가 -> A 삭제
// 2. B 추가 뒤집기 -> (앞이 B라면) 뒤집기, B 삭제
 
std::string A = {};
 
void Reverse(std::string& str)
{
	int iSize = str.size();
 
	for (int i = 0; i < iSize * 0.5; ++i)
	{
		char cTemp = str[i];
		str[i] = str[iSize - 1 - i];
		str[iSize - 1 - i] = cTemp;
	}
}
 
int main()
{
	std::string B = {};
 
	std::cin >> A >> B;
 
	std::queue<std::string> que = {};
 
	que.push(B);
	while (!que.empty())
	{
		std::string str = que.front();
		que.pop();
 
		if (A.size() == str.size())
		{
			if (A == str)
			{
				std::cout << 1;
				return 0;
			}
 
			else
				continue;
		}
 
		if (str.back() == 'A')
		{
			str.pop_back();
			que.push(str);
			str.push_back('A');
		}
 
		if (str.front() == 'B')
		{
			Reverse(str);
			str.pop_back();
			que.push(str);
		}
	}
 
	std::cout << 0;
 
	return 0;
}

queue를 이용해서 BFS로 뒤에서부터 계산