[C++]G5 백준 12904 - A와 B

1. 문제 링크

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

소요 시간 : 42분

시도 횟수 : 3

2. 문제 설명

난이도 : G5

사용 알고리즘 : BFS

주어진 2가지의 규칙만으로 문자열 S를 T로 바꿀 수 있는지 확인하는 문제

 

3. 초기 풀이 방식

문자열의 길이가 하나씩 길어지는 방향이고, 탐색 후에 일치하기만 하면 바로 결과값을 리턴하면 되겠다 싶었다.

BFS를 활용하면 되겠다 싶었다!(탐색 과정에서 문자열 길이 조건을 준다면 DFS로도 가능할 것 같음)

 

#include<iostream>
#include<string>
#include<queue>
#include<unordered_map>
#include<algorithm>

using namespace std;

unordered_map<string, bool> m;

bool bfs(string a, string b) {
	queue<string> q;
	q.push(a);
	m[a] = true;
	while (!q.empty() && q.front().size()<b.size()) {
		string tmp = q.front();
		q.pop();
		string tmp1 = tmp + 'A';
		reverse(tmp.begin(), tmp.end());
		string tmp2 = tmp + 'B';
		if (tmp1 == b || tmp2 == b) return true;
		else {
			if (!m[tmp1]) {
				m[tmp1] = true;
				q.push(tmp1);
			}
			if (!m[tmp2]) {
				m[tmp2] = true;
				q.push(tmp2);
			}
		}
	}
	return false;
}

int main() {
	string s, t;
	cin >> s >> t;
	cout << bfs(s, t);
}

결과 : 메모리 초과ㅜㅜ

 

4. 풀이 실패 원인 분석 + 해결

마지막에 tmp1, tmp2의 길이가 T와 같을 때에는 큐에 넣어봤자 정답이 아닐게 뻔하니 큐에 넣지 않도록 해봤으나 역시나 이건 주요 문제가 아니었다.

if (tmp1.size()!= b.size() && !m[tmp1]) {
    m[tmp1] = true;
    q.push(tmp1);
}
if (tmp2.size()!=b.size() && !m[tmp2]) {
    m[tmp2] = true;
    q.push(tmp2);
}

 

그래서 고민을 거듭한 결과...

T에서 S를 만들어볼까?

 

라는 생각을 하게 되었고, substr을 사용해서 긴 문자열을 점점 줄여나가는 방식으로 진행했다!

이렇게 하면 T의 범위를 벗어나는 문자열은 큐에 담기지 않기 때문에 메모리가 훨씬 절약될 것이라 생각했고,

결과는 성공 !

 

#include<iostream>
#include<string>
#include<queue>
#include<unordered_map>
#include<algorithm>

using namespace std;

unordered_map<string, bool> m;

bool bfs(string a, string b) {
	queue<string> q;
	q.push(b);
	m[b] = true;
	while (!q.empty() && q.front().size()>a.size()) {
		string tmp = q.front();
		q.pop();
		if (tmp[tmp.size() - 1] == 'A') tmp = tmp.substr(0, tmp.size() - 1);
		else {
			tmp = tmp.substr(0, tmp.size() - 1);
			reverse(tmp.begin(), tmp.end());
		}
		if (tmp == a) return true;
		else {
			if (tmp.size() > a.size() && !m[tmp]) {
				m[tmp] = true;
				q.push(tmp);
			}
		}
	}
	return false;
}

int main() {
	string s, t;
	cin >> s >> t;
	cout << bfs(s, t);
}

 

<오늘의 TMI>
나의 룸메는 알람으로 에스파 노래와 팝송, 기본 알림음 3개를 돌아가면서 사용한다.
그는 이따금씩 두시간 내내 알람이 울리는 경이로운 퍼포먼스를 선사했으며,
드디어 오늘 방을 빼는 듯한 움직임을 보였다. >야호<