YEJIN LEE

“Keep turnin’ the pages”

2 minute read

브루트포스 알고리즘

문제

수빈이는 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을 출력한다.

예제 입력 1 
A
BABA

예제 출력 1 
1

💻코드

  • 문제 풀이의 핵심이라고 생각되는 부분은 T를 S로 만들면서 바뀐 조건
    1. 문자열의 뒤에 A를 추가한다. ➡️ T의 마지막 문자가 A이면 제거한다.
    2. 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. ➡️ T의 맨 처음 문자가 B이면 제거하고 뒤집는다.
      이다.
  • 위 조건에 따라 경우의 수를 탐색하는 재귀함수가 필요하다.

  • 재귀가 무한 호출에 빠지지 않기 위한 종료조건으로 두 문자열이 같거나, S로 만들 수 없는 경우를 포함시켜야 한다.

  • 이 때, 입력받은 문자열 T를 그대로 수정해가며 쓰면 안되는데, 그 이유는 T에 위의 조건에 따라 변형하면서 되는지 안되는지 경우를 만들어보는데, T를 변형하면 다음 경우의 수를 따질 때 제대로 된 결과가 나올 수 없는 당연한 이야기가 있기 때문이고, 이것을 기록하는 이유는 나는 바보같이 그 생각을 하지 못했기 때문이다.

  • 또한, else if가 아닌 if를 사용해야한다. 그 이유는 첫 번째 조건에 맞아 떨어지고 두 번째 조건에도 해당되는 경우가 있을 수 있기 때문이다. 예제 입력1이 그런 경우이다. BABA에서 A를 제거해 BAB로 S를 만들어 보는 경우를 탐색해봐야 하고, B를 없애고 뒤집어 ABA로 S를 만드는 경우 또한 탐색해보아야 하기 때문이다.
/*
* [백준 12919] A와B 2
* 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 
* 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

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

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

* [알고리즘]
* 완전탐색 알고리즘 : 가능한 모든 경우의 수를 모투 체크해 정답을 찾는 방법
* 그리디와 자꾸 헷갈릴 때가 있는데, 그리디는 현 로컬 시점에서 최적해를 따라 최종적 해답에 이르는 방법이고, 
* 완전 탐색은 정말 경우 하나하나 다 따져보는 방법
* 
* 이 문제도 처음부터 A혹은 B를 붙이고 뒤집으며 S를 T로 만들기 보단 반대로 역추적하는 것이 더 효율적일 것 같다.
* T의 마지막 문자가 A면 없애준다
* T의 첫번째 문자가 B면 문자열을 뒤집고 마지막 B를 없애준다
*/

#include<iostream>	
#include<algorithm>
#include<vector>
#include<string>	

using namespace std;

void toAB(string s, string t) {
	if (s == t) {
		cout << 1;
		exit(0);
	}
	if (s.size() >= t.size()) return;
	if (t[t.size() - 1] == 'A') {
		string tmp = t;
		tmp.erase(tmp.size() - 1);
		toAB(s, tmp);
	}
	if (t[0] == 'B') {
		string tmp = t;
		tmp.erase(tmp.begin());
		reverse(tmp.begin(), tmp.end());
		toAB(s, tmp);
	}
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(NULL);	cout.tie(NULL);

	string S, T;
	cin >> S >> T;
	toAB(S, T);
	cout << 0;

	return 0;
}
  • 처음 문제를 읽고 풀이를 생각할 때, S에서 T를 가기에는 경우의 수가 2제곱으로 늘어나기에 T에서 S로 변환해야 겠다는 생각은 쉽게 할 수 있었다. 또한 완전 탐색 알고리즘으로 접근하기 위해서는 결국 문제에서 제시하는 조건 두 가지를 거꾸로 바꿔 하나씩 적용해가며 경우의 수를 따져보아야 한다는 생각이 들었지만, 어떻게 모든 경우의 수를 따지며 재귀의 방법을 써야하는지는 그림이 그려지지 않아 어려웠다.

You may also enjoy