[백준/BOJ] 백준 21776번 : 가희와 읽기 쓰기 놀이

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

21776번: 가희와 읽기 쓰기 놀이

백트래킹을 이용해서 나올 수 있는 순서의 경우를 모두 확인하여 문제를 해결했다

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <set>
using namespace std;

int n, c;
vector<vector<int>> order; //해당 사람이 낸 카드 순서
vector<string> card;
set<string> result;
set<string>::iterator it;

void Solve(vector<int>& check_index, string maked)
{
	bool finish = true;

	for (int i = 0; i < check_index.size(); i++)
	{
		//i번째 플레이어의 연산을 실행할때
		//i번째 플레이어가 다음에 고를 순서
		int can_check_index = check_index[i];

		//i번째 플레이어의 플레이는 끝났을때
		if (can_check_index >= order[i].size())
			continue;

		finish = false;

		string this_maked = maked;

		//i번째 플레이어의 can_check_index카드를 실행한다
		string this_card = card[order[i][can_check_index]];

		stringstream ss(this_card);
		string temp;
		vector<string> temps;

		bool error_check = false;

		while (getline(ss, temp, ','))
		{
			temps.push_back(temp);
		}

		//temps순서로 연산을 실행한다
		for (int j = 0; j < temps.size(); j++)
		{
			if (temps[j][0] == 'A')
			{
				this_maked += temps[j][temps[j].size() - 1];
			}

			else if (temps[j][0] == 'D')
			{
				int index = stoi(temps[j].substr(temps[j].size() - 1, 1));

				//index번째 문자가 있을때
				if (index < this_maked.size())
				{
					string left = this_maked.substr(0, index);
					string right = this_maked.substr(index + 1, this_maked.size() - (index + 1));
					this_maked = left + right;
				}

				//index번째 문자가 없을때
				else
				{
					//ERROR
					error_check = true;
					break;
				}
			}
		}

		//해당 연산으로 인해 ERROR가 실행될때
		if (error_check == true)
		{
			result.insert("ERROR");
			continue;
		}

		check_index[i]++; //해당플레이어가 다음에 뽑을 카드는 그 다음것이다

		Solve(check_index, this_maked);

		//원상복구
		check_index[i]--;
	}

	//모든 연산이 끝난 경우일때
	if (finish == true)
	{
		if (maked.size() == 0)
			result.insert("EMPTY");
		else
			result.insert(maked);
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> c;

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;

		vector<int> inputs;
		for (int j = 0; j < num; j++)
		{
			int input;
			cin >> input;

			//카드 번호를 0번부터 한다
			inputs.push_back(input - 1);
		}
		order.push_back(inputs);
	}

	cin.ignore();
	for (int i = 0; i < c; i++)
	{
		string input;
		getline(cin, input);

		card.push_back(input);
	}

	vector<int> check_index;
	for (int i = 0; i < n; i++)
	{
		check_index.push_back(0);
	}

	Solve(check_index, "");

	for (it = result.begin(); it != result.end(); it++)
		cout << *it << "\n";

	return 0;
}