백준 BOJ 12919 - A와 B 2

실버골드 랜덤디펜스

BFS를 사용해서 풀어보았다.

 

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

12919번: A와 B 2

 

처음에는 S에서 시작해서 T로 문자열을 하나씩 붙여가면서 완탐을 돌릴 생각을 했는데,

S.length() 가 1이고 T.length()가 50인경우에는 메모리초과가 발생하게 된다.

 

그래서 미리미리 불가능해보이는 경우의 수는 쳐낼생각을 해야 하는데,

생각을 정 반대로 바꿔서

 

T에서 시작해서 S로 문자열을 하나씩 잘라가면서 완탐을 해주면 된다.

이 경우에는

1. 문자열의 제일 끝자리가 A이거나

2. 문자열의 제일 앞자리가 B이여야만 한다.

라는 제약조건이 생기기 때문에

완전탐색을 해도 시간초과나 메모리초과를 받지 않고 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

unordered_map<string,int> m;
queue<string> q;

string st,ed;
int N;

void bfs(string s){
	string now, nxt;
	int len;
	
	q.push(s);
	m[s] = 1;
	
	while(!q.empty()){
		now = q.front(); q.pop();
		len = now.length();
		
		if(now[0] == 'B'){
			nxt = now.substr(1);
			reverse(nxt.begin(), nxt.end());
			
			if(m[nxt] == 0 && nxt.length() >= N){
				q.push(nxt);
				m[nxt] = 1;
			}
		}
		
		if(now[len-1] == 'A'){
			nxt = now.substr(0,len-1);
			
			if(m[nxt] == 0 && nxt.length() >= N){
				q.push(nxt);
				m[nxt] = 1;
			}
		}
	}
	return;
}

int main(){
	cin >> st >> ed;
	N = st.length();
	
	bfs(ed);
	
	cout << m[st];
	
	return 0;
}