C++ / 백준 / 2800 / 괄호 제거

문제

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

2800번: 괄호 제거

문제풀이

큰 틀은 DFS이다.

stack<pair<int, int>>bracket은 괄호 '('와 해당 위치를 저장하기 위한 용도,

set<string>answer는 중복 제거된 값들을 저장하는 용도,

string input은 입력값,

vector<bool>remove는 True값이면 괄호를 지운다는 의미, False이면 지우지 않는다는 의미를 나타내는 용도이다.

 

0번째 인덱스부터 DFS를 시작한다.

스택을 이용하여 '(' 발견 시 bracket.first에 ( 입력, bracket.second에는 몇 번째 인덱스인지 값을 저장한다.

')'발견 시 (의 위치를 num에 저장하고 pop을 한다.

그다음 방금 발견한 괄호 한쌍을 지우지 않고 넘어가는 DFS문을,

지우고 넘어가기 위해 remove[num]과 remove[idx]의 값을 True로 바꾸고 DFS문 실행한다.

현재 값이 괄호가 아닌 나머지 값이면 idx+1을 하고 DFS문을 실행한다 (다음칸으로 이동).

idx가 input.size와 같다면 문자열을 다 방문했으므로 remove값에 따라 string 값을 만들고 answer에 집어넣는다.

모든 DFS문이 종료되면 첫 번째 answer(입력값과 동일)을 제외하고 모두 출력한다.

 

코드

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
string input;
set<string>answer;

void DFS(int idx, vector<bool>remove, stack<pair<char, int>>bracket) {
	if (idx == input.size()) {
		string ans("");
		for (int idx2 = 0; idx2 < input.size(); ++idx2) {
			if (!remove[idx2])
				ans += input[idx2];
		}
		answer.insert(ans);
	}
	else if (input[idx] == '(') {
		bracket.push({ '(',idx });
		DFS(idx + 1, remove, bracket);
	}
	else if (input[idx] == ')') {
		int num = bracket.top().second;
		bracket.pop();
		DFS(idx + 1, remove, bracket);
		remove[num] = true;
		remove[idx] = true;
		DFS(idx + 1, remove, bracket);
	}
	else {
		DFS(idx + 1, remove, bracket);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> input;

	vector<bool>remove(input.size(), false);
	stack<pair<char, int>>bracket;

	DFS(0, remove, bracket);
	set<string>::iterator iter;

	iter = answer.begin();
	iter++;
	for (iter; iter != answer.end(); iter++)
		cout << *iter << '\n';
}