백준 - 1705번 컵

문제

A B 명령어에 따라 공 위치를 이동 시킬 수 있다
어떤 컵 위치에서 시작하든 첫번째 컵에 공이 들어가도록 하는 명령어를 찾아라

생각

어떤 컵 위치에서 시작되어도 알맞게 작동되어야 하니까,
모든 컵의 위치에서 시작해보고 다 첫번째로 들어가는지 확인해보는 식으로 코드를 짬!

아이디어 1

지금까지의 명령어, 이 명령어에 따른 상태들을 저장하고,
("", 모든 컵의 상태)로 시작해서
("~어쩌구저쩌구~", {1}) 로 끝나는 어쩌구저쩌구 명령어를 찾자

queue<pair<string, vector<int>>> q;
pair<string, vector<int>> temp;
//명령어 문자열, 했을 때 조합

...
vector<int> begin;
for (int i = 0; i < n; i++) {
	begin.push_back(i+1);
}
q.push(make_pair("", begin));

while (1) {
	temp = q.front();
	makeNewCombi(temp.first, temp.second, "A");
	makeNewCombi(temp.first, temp.second, "B");
	if (flag) break;
	q.pop();
}

아이디어 2

끝없이 같은 상태 변화를 빙글빙글 돌면서 안 끝나는 걸 방지하기 위해
이미 나온 조합이면 더 이상 탐색을 안 하기러했다
문제 요구는 최소 명령어가 아니긴 하지만,
같은 상태일 때 짧은 명령어로 도착한걸로만 생각하는게 큐에도 안 들어갈 수 있음!

여기서 모든 컵에 넣어둔 애가
어찌저찌~ 해서
1번 컵에 2개, 2번 컵에 1개, 4번 컵에 1개 가 있는 상태나
1번 컵에 1개, 2번 컵에 2개, 4번 컵에 1개 가 있는 상태는
사실상 모두다 1에 도착하려면 명령어는 같으니까!!
몇 개 들어있는지는 저장안하구,
어느 컵에 들어있는지 아닌지만 저장했다.

vector<vector<int>> combination;
//지금까지 겪은 모든 조합을 기록

q.push(make_pair(newStr, newCombi));
//기존에 없는 조합일 때

시간 초과 1

아이디어 2를 다음과 같이 구현했다

check 배열에 나온 적 있는지 저장해서 맨 처음 등장한 수만 벡터에 달아줌
(중복 값이 없는 벡터를 만들기 위해)

	int check[505] = { 0, }; //벡터에 중복된 값을 안 넣기 위해
	vector<int> newCombi;
	for (int i = 0; i < preCombi.size(); i++) {
		int newpos = t[preCombi[i]];
		if (check[newpos]== 0) {
			//처음 나온 위치
			newCombi.push_back(newpos);
			check[newpos] = 1;
		}
	}
	sort(newCombi.begin(), newCombi.end());

지금까지 모든 조합들을 돌면서 같은게 있으면 추가 안하고 함수 리턴

	for (int i = 0; i < combination.size(); i++) {
		if (combination[i] == newCombi) {
			return false;
		}
	}

오 시간 초과가 난다!

시간 초과 2

새로운 조합 만드는거랑, 조합이 이미 나온건지 찾는게 느린 것 같아서

벡터를 쭉 먼저 만들고 중복 삭제하게,
벡터 find 함수를 써서 찾게 코드를 고쳐보았다.

	vector<int> newCombi;
	for (int i = 0; i < preCombi.size(); i++) {
		newCombi.push_back(t[preCombi[i]]);
	}
	sort(newCombi.begin(), newCombi.end());
	newCombi.erase(unique(newCombi.begin(), newCombi.end()), newCombi.end());
    
    	...
   	if (find(combination.begin(), combination.end(), newCombi) == combination.end()) {
		combination.push_back(newCombi);
		q.push(make_pair(newStr, newCombi));
	}

그래도 시간 초과! 웃긴 시도다ㅋㅋㅋ

시간 초과 3

위에까지 시도하고 개빡쳐서 그만뒀다ㅜㅜ

그러다가 탑싯 공부를 하고있었는데
서치 종류에 대해 배우다가 사전식(?) 검색을 보았다
있을 것 같은 곳에 가서 서치하는 방법!(다람쥐면 ㄷ에가서 쭈욱 서치)

이럴수가 나는 파악했다...
기존 나온 조합들을 길이별로 나눠서 관리하면 찾을 때 편하지 않을까..?

//vector<vector<int>> combination;
vector<vector<int>> combination[505];
//나온 조합의 길이가 [i]인 애들을 달아놓자!

...
if (find(combination[newCombi.size()].begin(), combination[newCombi.size()].end(), newCombi) == combination[newCombi.size()].end()) {
	combination[newCombi.size()].push_back(newCombi);
	q.push(make_pair(newStr, newCombi));
}

응~ 그래도 시간 초과야~

메모리 초과 1

이젠 새로운 에러.. 하하핳하하ㅏㅎ

어디선가 배웠던 것 같은 것이 떠올랐다.. 그건 바로.. !!!!!set!!!!!
중복을 허용하지 않고 저장하며, 삽입 시 트리 구조로 정렬되서 입력
그렇다 딱 나한테 필요한거네 하고 와.. 이거다.. 이건 진짜 된다!! 라는 마음으로 도전

set<vector<int>> combination[505];
//vector<vector<int>> combination[505];
//지금까지 겪은 모든 조합을 기록

...
	//중복이 없어서 성공적으로 저장이 되면 p.second 가 true, 아니면 false
	auto p = combination[newCombi.size()].insert(newCombi);
	if (p.second) {
		q.push(make_pair(newStr, newCombi));
	}

오~ 이렇게 하니까 헤헤ㅔ 새로운 에러를 만났다
내 머리로는 왠지 이해가 안 되는겨?
그래서 머리를 아주 굴려보니 난 알게되었다.

vector가 아닌 set을 써서
아주 빨리 빨리 빨리 처리를 하니까
시간 초과가 되기 전에 메모리 초과가 되어버린거임.
개멋져 내 추론

위에 내가 시간초과를 해결하기 위해 노력한 코드가
------시간초과------메모리초과----->
이런 운명이였었는데,,

set 써서 시간 초과 문제를 해결(?)해서
좀 빨라지니까 큐에 엄청 넣고, 나온 조합들 기록에 정보도 엄청 넣어서 터져버리는겨..

힝.. 1

여기서 포기하긴 너무 많이 와버린 나.
놓지 못하고 계속 생각하는데,,,

1. int를 short로 바꿔볼까 ㅎㅎㅎㅎㅎ 500개 컵이니까ㅎㅎㅎㅎ
   (알골 잘 알이 그랫는데 정말 조금의 메모리 초과로
   메모리 초과 에러가 뜨기 쉽지않댄다.
   100이 제한이였으면 400으로 메모리 초과라기보단,
   어마무시하게 넘겨버리는 코드일세!! 나는 어마무시해~~)

2. 모든 나왔던 조합말고,, 최근 조합이랑 먼저 비교했다가 그 다음 모든 조합..?

3. 힝.. 기존 나왔던 조합들.. 인트 백터들인데..
   이 값을 돌며 정렬하면서 트리로 저장해서 힘든가..? 스트링으로 저장하면 좀 낫냐????!!?!?

아 이런 생각들은 내가 다시봐도 ㅋㅋㅋㅋ웃기고 잘 모르겠어서 안했다

힝.. 2

푼 사람이 없어서 정보도 너무 없궁..
솔루션을 겨우 찾았는데 다음과 같은 말

솔루션 참고

The problem can be modeled with a finite state automaton, where each cup has its own state, and there are exactly two transitions from each state, one for each letter
오 마이갓 나 오토마타 러버임! 그러게 오토마타네? (전혀 생각 못했었음 그 전엔)

When the game starts, we don't know which state the automaton is in, so we say that all states are possible. We need to find an input sequence which will make state 1 the only possible state.
와우 내 생각이랑 세임

If we choose a pair of states (A, B) and find a sequence of letters which takes the automaton from state A to state 1, and from state B to state 1, then that sequence of letters must reduce the number of possible states.
나 잘 이해한건지 모르겠는데 2랑 3 컵에서 어떤 명령어에 의해서 1컵에 들어온 걸 찾아?!
나는 모든 애들이 다 1에 오는지 봤는데
1이 될 수 있는 집합,
이러한 집합이 될 수 있는 또 상위 집합,
이 ㅅ..집합의 집합.. 이렇게 모두 다 커버가능한지 보는 방법도 있겠구만
(그래서 이번엔 이렇게 짜보기로 결심함)

The idea of the solution is to maintain the set of possible states, then repeatedly choose some two states, find an input sequence whZ, and calculate the new set of possible states (which is surely smaller than previously).
근데 여기서 보면 "smaller 집합" 이라는데
기존에 내가 풀던 방식 이야기 같은데!!
모든 경우에서 하나가 다른 하나로 상태가 바뀌는거니까 점점 작아지고 있맨..

(아니 근데 조금은 커졌다가 다시 엄청 작아질 수도 있지않나?
로컬 미니멈.. 아니 더이상 머리가 안 돌아간다 안해!~!!
큰 상태에서 작아질거였으면 이미 했던 경우인가? 아니 생각안해..)

코드 시도

index로 올 수 있는 애들을 저장
1에서 시작해서 모든 케이스로 올 수 있는지 봐

vector<int> ac[505];
vector<int> bc[505];
//a, b에 따라서 index에로 올 수 있는 애들

...
for (int i = 1; i <= n; i++) {
	allCase.push_back(i);
}
//1에서 시작해서 모든 조합으로 부터 올 수 있게 해! allcase가 되는게 꿈
	
vector<int> firstState = { 1 };
q.push(make_pair("", firstState));

그래두 비슷하게 에러나는 것 같다
그냥 어디까진 set으로 어디까진 vector로 하냐에따라 에러달랑

알골 잘 알 선배한테 물어보니까
사람들이 많이 안 푼건 놓아주래요..
이제 저는 이 문제를 놓아줄 때가 되었어요..
논리는 어느정도 맞은 것 같으니.. 맞은걸로 해도될까요? 저?

코드

1. 모든 시작에서 1이 되냐?

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

queue<pair<string, vector<int>>> q;
pair<string, vector<int>> temp;
//명령어 문자열, 했을 때 조합
vector<vector<int>> combination[505];
//지금까지 겪은 모든 조합을 기록

int ak[505];
int bk[505];

int n;
string returnStr = "";
vector<int> wantCombi = { 1 };

//기존 문자열과 조합으로 새로운 문자열 만들어 나가기
void makeNewCombi(string preStr, vector<int> preCombi, string newStr) {
	int check[505] = { 0, }; //벡터에 중복된 값을 안 넣기 위해
	vector<int> newCombi;
	for (int i = 0; i < preCombi.size(); i++) {
		if (newStr == "A") {
			int newpos = ak[preCombi[i]];
			if (check[newpos] == 0) {
				//처음 나온 위치
				newCombi.push_back(newpos);
				check[newpos] = 1;
			}
		}
		else if (newStr == "B") {
			int newpos = bk[preCombi[i]];
			if (check[newpos] == 0) {
				//처음 나온 위치
				newCombi.push_back(newpos);
				check[newpos] = 1;
			}
		}
	}
	sort(newCombi.begin(), newCombi.end());
	//newCombi.erase(unique(newCombi.begin(), newCombi.end()), newCombi.end());

	newStr = preStr + newStr;

	if (newCombi == wantCombi) {
		returnStr = newStr;
	}

	if (find(combination[newCombi.size()].begin(), combination[newCombi.size()].end(), newCombi) == combination[newCombi.size()].end()) {
		combination[newCombi.size()].push_back(newCombi);
		q.push(make_pair(newStr, newCombi));
	}
}

void findString() {
	bool flag = false;
	vector<int> begin;
	for (int i = 0; i < n; i++) {
		begin.push_back(i + 1);
	}
	combination[n].push_back(begin);
	q.push(make_pair("", begin));

	while (1) {
		temp = q.front();
		makeNewCombi(temp.first, temp.second, "A");
		makeNewCombi(temp.first, temp.second, "B");
		if (returnStr != "") break;
		q.pop();
	}
}

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &ak[i + 1], &bk[i + 1]);
	}

	findString();
	cout << returnStr;

	return 0;
}

2. 1에서 모든 조합이 되냐?

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

queue<pair<string, set<int>>> q;
pair<string, set<int>> temp;
//명령어 문자열, 했을 때 조합
set<set<int>> combination[505];
//vector<vector<int>> combination[505];
//지금까지 겪은 모든 조합을 기록

int ak[505];
int bk[505];

int n;
string returnStr = "";
set<int> wantCombi = { 1 };

//기존 문자열과 조합으로 새로운 문자열 만들어 나가기
void makeNewCombi(string preStr, set<int> preCombi, string newStr) {
	set<int> newCombi;

	set<int>::iterator iter;
	for (iter = preCombi.begin(); iter != preCombi.end(); iter++) {
		int tc[505];
		if (newStr == "A") {
			newCombi.insert(ak[*iter]);
		}
		else {
			newCombi.insert(bk[*iter]);
		}
	}

	newStr = preStr + newStr;

	if (newCombi.size() == 1) {
		if (newCombi == wantCombi) {
			returnStr = newStr;
		}
	}

	auto p = combination[newCombi.size()].insert(newCombi);
	if (p.second) {
		q.push(make_pair(newStr, newCombi));
	}
}

void findString() {
	set<int> begin;
	for (int i = 0; i < n; i++) {
		begin.insert(i + 1);
	}
	combination[n].insert(begin);
	q.push(make_pair("", begin));

	while (1) {
		temp = q.front();
		makeNewCombi(temp.first, temp.second, "A");
		makeNewCombi(temp.first, temp.second, "B");
		if (returnStr != "") break;
		q.pop();
	}
}

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &ak[i + 1], &bk[i + 1]);
	}

	findString();
	cout << returnStr;

	return 0;
}