[ 프로그래머스 올바른 괄호의 갯수 (Lv4) ] (C++)

프로그래머스의 올바른 괄호의 갯수(Lv4) 문제이다.

[ 문제풀이 ]

본인은 완전탐색으로 문제에 접근하였다. 그 중에서도 특히 깊이우선탐색(DFS)를 이용해서 접근하였다.

먼저, '올바른 괄호'가 되기 위한 몇 가지 조건과 탐색할 때의 조건부터 알아보자.

1. 전체 괄호의 갯수

- 우리는 n개의 괄호쌍으로 만들 수 있는 올바른 괄호의 갯수를 구해야 한다. 그렇다면, n이라는 값이 주어진다면, 우리는 총

   몇 개의 괄호를 이용해서 올바른 괄호를 만들어야 할까 ??

   바로, n * 2 개이다. n = 2 라고 주어졌을 경우, 이는 2개의 괄호쌍을 의미하는 것이고, '( ) ( )' 이와 같은 형태일 것이다.

   실제로 사용되는 괄호의 총 갯수는 n * 2 개가 된다.

2. 탐색 중, 현재 상태에서의 '여는 괄호의 갯수' or '닫는 괄호의 갯수'

- 위에서 말했듯이 모든 경우를 탐색해 보기 위해서 탐색을 하고 있는 중이라고 가정해보자.

   그런데, '여는 괄호의 갯수' or '닫는 괄호의 갯수'만 보고도 더 이상 탐색을 하지 않아도 되는 경우가 있다.

   어떤 경우가 이 경우에 해당하는지 알아보자.

   예를 들어서 n = 2 라고 가정해보자. 우리는 2개의 괄호쌍으로 올바른 괄호를 만들어야 하고, 그 올바른 괄호로는

   { '( ) ( )' , '( ( ) ) ' } 이렇게 2개가 존재한다.

   그럼 탐색하는 도중에, 여는 괄호의 갯수가 3개가 되었을 때를 생각해보자.

   우리는 총 n * 2개, 즉, 4개의 괄호를 이용해서 올바른 괄호를 만들려고 노력하고 있는데, 탐색 도중, 여는 괄호의 갯수가 3개가

   되어 버린다면 더 이상의 탐색이 의미가 있을까 ?? 탐색이 의미가 없을 것이다. 왜냐하면, 우리는 4개의 괄호를 이용해서

   올바른 괄호를 만들어야 하고, 올바른 괄호가 되려면 4개의 괄호 중에서 2개는 여는괄호, 2개는 닫는 괄호가 되어야만

   올바른 괄호가 될 '가능성' 이 있기 때문이다. 무조건 올바른 괄호가 되는 것은 아니다. 극단적으로 ' ) ) ( ( ' 는 4개 중

   2개가 여는괄호, 2개가 다는 괄호이지만 올바른 괄호는 아니기 때문이다.

   마찬가지로, 닫는 괄호의 갯수 또한 3개가 되어버린다면, 올바른 괄호가 될 가능성이 전혀 없는 탐색이기 때문에 끝까지 탐색을

   해볼 필요가 없다.

   즉 ! n개의 괄호쌍으로 올바른 괄호를 만들 수 있는 가능성 있는 탐색을 하려면 "여는 괄호 or 닫는 괄호의 갯수가 항상 n / 2 개

   보다 작거나 같아야 한다." 라는 것이다.

   다시한번 말하지만, 위의 조건을 만족했다고 무조건 올바른 괄호가 되는 것은 아니다. ') ) ( ( ' 와 같이, 위에서 말한 조건을

   만족했지만, '올바른 괄호가 되지 않을 가능성' 또한 존재한다.

   그렇기 때문에 ! 위에서 말한 ') )  ( ('와 같은 경우도 걸러주자. ') ) ( (' 이 괄호가 왜 잘못된 괄호인지를 생각해보자.

   아마, 여는 괄호와 닫는 괄호의 쌍이 맞지 않기 때문이다. 닫는 괄호 입장에서는 닫기 전에 열어뒀던 괄호가 없고, 여는 괄호

   입장에서는 열었는데 닫은 괄호가 없기 때문이다. 즉 ! 닫는 괄호가 추가되기 위해서는 그전에 반드시 "여는 괄호"가 존재해야

   한다는 것이다. 좀 더 정리해서 이야기해보면 "닫는 괄호의 갯수는, 항상 여는 괄호의 갯수보다 작아야 한다." 라는 것이다.

  

   본인은 위에서 말한 2가지 경우에는 더 이상의 탐색을 진행하지 않도록 걸러주면서 깊이 우선탐색을 진행하였다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int Answer;
 
void DFS(int Open, int Close, int Cnt, int Total)
{
    if(Open > Total / 2 || Close > Total / 2) return;
    if(Close > Open) return;
    if(Cnt == Total)
    {
        Answer++;
        return;
    }
    
    DFS(Open + 1, Close, Cnt + 1, Total);
    DFS(Open, Close + 1, Cnt + 1, Total);
}
 
int solution(int n) 
{
    DFS(0, 0, 0, n * 2);
    return Answer;
}