C++로 잘못된 괄호 제거하기: BFS를 활용한 모든 유효한 괄호 시퀀스 찾기

괄호 시퀀스가 주어졌을 때, 잘못된 괄호를 제거하여 만들 수 있는 모든 유효한 괄호 조합을 출력해야 합니다. 아래 예시를 통해 문제를 살펴보겠습니다.

입력 : str = "()())()"
출력 : ()()() (())()
가능한 해답은 두 가지입니다.
"()()()" 와 "(())()"

입력 : str = "(v)())()"
출력 : (v)()() (v())()

이 문제는 백트래킹(backtracking) 기법을 활용하여 모든 유효한 시퀀스를 출력하는 방식으로 해결할 수 있습니다.

문제 해결 접근법

이 접근법에서는 BFS(너비 우선 탐색)를 사용하여 여는 괄호와 닫는 괄호를 하나씩 차례로 제거해 봅니다. 그런 다음 각 시퀀스가 유효한지 검사하고, 유효하다면 해당 문자열을 결과로 출력합니다. BFS를 활용하면 최소 개수의 괄호를 제거하여 만들 수 있는 모든 유효한 조합을 빠짐없이 찾을 수 있다는 장점이 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
bool isParenthesis(char c){
    return ((c == '(') || (c == ')'));
}
bool validString(string str){
    int cnt = 0;
    for (int i = 0; i < str.length(); i++){
        if (str[i] == '(')
           cnt++;
        else if (str[i] == ')')
           cnt--;
        if (cnt < 0)
           return false;
    }
    return (cnt == 0);
}
void validParenthesesSequences(string str){
    if (str.empty())
        return ;
    set<string> visit; // 이미 확인한 문자열을 저장하여 중복 검사를 방지
    queue<string> q;   // BFS 수행을 위한 큐
    string temp;
    bool level = false;
    // 주어진 문자열을 시작 노드로 큐에 삽입
    q.push(str);
    visit.insert(str);
    while (!q.empty()){
        str = q.front(); q.pop();
        if (validString(str)){
            cout << str << "\n"; // 유효한 문자열 출력
            level = true; // 현재 레벨에서 유효한 문자열을 찾았으므로 더 깊이 탐색하지 않음
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++){
            if (!isParenthesis(str[i])) // 괄호가 아닌 문자는 제거하지 않음
                continue;
            temp = str.substr(0, i) + str.substr(i + 1); // 문자열에서 괄호를 하나씩 제거
            if (visit.find(temp) == visit.end()) { // 아직 확인하지 않은 문자열만 큐에 삽입
                q.push(temp);
                visit.insert(temp);
            }
        }
    }
}
int main(){
    string s1;
    s1 = "(v)())()";
    cout << "Input : " << s1 << "\n";
    cout << "Output : ";
    validParenthesesSequences(s1);
    return 0;
}

실행 결과

Input : (v)())()
Output : (v())()

코드 설명

위 코드는 주어진 문자열을 시작 노드로 삼아 BFS를 수행합니다. 큐에서 문자열을 꺼낼 때마다 유효성을 검사하고, 유효하다면 즉시 출력합니다. 동시에 set 자료구조(visit)에 이미 확인한 시퀀스를 기록하여 동일한 문자열을 중복해서 검사하지 않도록 합니다. 또한 괄호가 아닌 일반 문자(예: 'v')는 제거 대상에서 제외합니다. 같은 레벨에서 유효한 시퀀스를 한 번이라도 찾으면 그 이상 깊게 탐색하지 않는데, 이는 최소한의 괄호만 제거한 결과만을 얻기 위함입니다.

마무리

이번 글에서는 잘못된 괄호 제거(Remove Invalid Parentheses) 문제를 BFS 기반 백트래킹으로 해결하는 방법과 이를 구현한 C++ 코드를 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮길 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.