백준 - A와 B 2 (C++)

Pixabay로부터 입수된 Gerd Altmann님의 이미지 입니다.

 

---

 

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

12919번: A와 B 2

 

 이번 문제는 A, B로만 구성된 단어 S와 T가 주어졌을 때, 주어진 두 가지 방법으로만 T를 만들 수 있는지를 판별하는 문제이다. 이번 문제의 경우, 재귀를 통해 각 경우들을 일일이 체크하면 답을 무조건 찾을 수 있다. 하지만 적절한 탈출 조건이 없을 경우 재귀를 무한히 진행할 수도 있다. 그렇기에 적절한 탈출 조건을 설정해야 한다.

 

 우선 재귀를 실행할 함수의 구조를 생각해보자. 이 함수는 문자열 변수를 인자로 받을 것이다. 만약 이 단어가 T와 같을 경우, 함수를 종료한다. 그리고 이 단어의 뒤에 'A'를 붙인 단어와 뒤에 'B'를 붙이고 뒤집은 단어를 이용해 다시 함수를 실행할 것이다. 

 

// T를 만들 수 있으면 true를, 아니면 false를 반환
bool Check(string word)
{
	if (word == T)
		return true;

	if (word.length() >= T.length())
		return false;

	bool result = Check(word + 'A');

	if (result == true)
		return true;
	
    word += 'B';
    
	reverse(word.begin(), word.end());

	result = Check(word);

	return result;
}

아마 이런 식으로 함수의 코드를 작성할 수 있을 것이다. 단어 word를 입력받은 후, 단어가 T와 같다면 true를 반환하고 종료한다. 그 후, word의 길이가 T의 길이와 같거나 길 경우 false를 반환한다. false만 반환하는 이유는, 이미 T인 경우는 이 함수의 맨 처음에 검사를 했기 때문이다. 그리고 S의 뒤에 'A'를 붙인 단어와 S의 'B'를 뒤에 붙이고 뒤집은 단어를 검사한다. 

 

 하지만 이 코드는 시간 초과가 뜬다. 아마 쓸 데 없는 경우까지 모두 실행하기 때문일 것이다. 만약 S가 "B"이고 T가 "BBB...BBB"일 경우, 'A'를 붙일 필요가 없다. 하지만 저 함수는 S에 'A'를 붙인 경우까지 탐색할 것이다. 이런 식으로 확인하지 않아도 되는 경우도 전부 확인하기 때문에 시간 초과가 발생한 것 같다. 그렇기에 탐색을 거꾸로, T를 S로 만들 것이다.

 

// T를 만들 수 있으면 true를, 아니면 false를 반환
bool Check(string word)
{
	if (word == S)
		return true;

	if (word.length() <= S.length())
		return false;

	if (word.back() == 'A')
	{
		string nextWord = word.substr(0, word.length() - 1);
		
		bool result = Check(nextWord);
		
		if (result == true)	
			return true;
	}

	if (word.front() == 'B')
	{
		string nextWord = word.substr(1, word.length() - 1);
		reverse(nextWord.begin(), nextWord.end());

		bool result = Check(nextWord);
		
		if (result == true)	
			return true;
	}

	return false;
}

 T에서 S를 만들 수 있을 경우 true를 반환하고 그렇지 않으면 false를 반환한다. 원래는 S에서 T를 만들기 위해서 S 뒤에 'A'를 붙이거나 S 뒤에 'B'를 붙인 후 뒤집을 수 있었다. 즉, 역으로 T에서 S를 만들기 위해서는 뒤의 'A'를 제거하거나 앞의 'B'를 제거한 후 뒤집어야 한다. 이를 위해 각 위치에 'A', 'B'가 있는 경우에만 진행할 수 있게 코드를 작성하였다. 이렇게 탐색을 진행한다면 앞에서 예를 들었던, S가 "B"이고 T가 "BBB...BBB"일 경우에 'A'를 제거하는 동작은 실행하지 않을 것이다. 이를 이용한 전체 코드는 다음과 같다.

 

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

string S, T;

bool Check(string word)
{
	if (word == S)
		return true;

	if (word.length() <= S.length())
		return false;

	if (word.back() == 'A')
	{
		string nextWord = word.substr(0, word.length() - 1);
		
		bool result = Check(nextWord);
		
		if (result == true)	
			return true;
	}

	if (word.front() == 'B')
	{
		string nextWord = word.substr(1, word.length() - 1);
		reverse(nextWord.begin(), nextWord.end());

		bool result = Check(nextWord);
		
		if (result == true)	
			return true;
	}

	return false;
}

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

	cin >> S;
	cin >> T;

	bool result = Check(T);

	cout << (result ? 1 : 0) << endl;

    return 0;
}