[C++] 백준 2800번 : 괄호 제거

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

2800번: 괄호 제거

---

 문제 풀이

DFS로 문자열을 구현하면 되는 문제였다.

check 함수를 통해서 백트래킹 중 일정 조건을 만족시킬 때  셋에 값을 추가하도록 한다.

사전 배열로 출력하기 위해서 set을 사용했다!

 느낀 점

처음에 갈피를 제대로 못 잡아서 살짝 헤매던 문제이다. 조금 생각해보니 전형적인 백트래킹 문제였다. 또, 자료구조인 척하는데 딱히 자료구조 같지는 않다.

 코드

#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <string>
#include <utility>

using namespace std;

string str;
vector<pair<int, int>> v;
stack<int> st;
set<string> s;
bool check[201];

void DFS(int n, int cnt) {
	if (n == v.size()) {
		if (cnt > 0) {
			string tmp = "";
			for (int i = 0;i < str.length();i++) {
				if (check[i]) tmp += str[i];
			}
			s.insert(tmp);
		}
		return;
	}
	else {
		DFS(n + 1, cnt);

		check[v[n].first] = false;
		check[v[n].second] = false;

		DFS(n + 1, cnt + 1);

		check[v[n].first] = true;
		check[v[n].second] = true;
	}
}


int main() {
	cin >> str;

	for (int i = 0; i < str.length();i++) {
		check[i] = true;

		if (str[i] == '(') st.push(i);
		else if (str[i] == ')') {
			v.push_back(make_pair(st.top(), i));
			st.pop();
		}
	}

	DFS(0, 0);

	for (auto iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << "\n";
	}
}