백준: 2800 괄호 제거

문제

2800번: 괄호 제거

 

문제 풀이

 문제를 풀기 위해서는, 괄호가 제거 가능한 경우 모두를 체크하여야 함을 알 수 있다. 따라서, 올바른 괄호를 이루는 경우를 판단하고 이에 따라 `DFS`를 통해 가지를 뻗어나가야 한다. 

 

• `DFS`에서 어떤 경우가 올바른 괄호인지 알 수 없으므로, 미리 체크를 한다.
  • 이는 `stack`을 사용하며, 올바른 괄호를 판단하는 로직에서, 어떤 경우 인지 기록하는 경우만 추가하면 된다.
• `DFS`를 통해 다음과 같은 경우를 가지치기 한다.
  • 괄호를 지우는 경우와 지우지 않는 경우로 나뉜다.
  • 답이 되는 문자열을 구성할 때 백 트랙킹이 가능하도록, `append`, `pop`을 활용한다.

 

코드

from sys import stdin


def dfs(cur_idx, depth):
    global answer, sub_value

    if cur_idx == depth:
        # 입력 값 (수식)은 제외.
        if ''.join(sub_value) != ''.join(string):
            answer.add(''.join(sub_value))
        return

    is_bracket = string[cur_idx]

    # 여는 괄호인 경우
    if is_bracket == '(':
        check[cur_idx] = True
        dfs(cur_idx + 1, depth)
        check[cur_idx] = False

    # 닫는 괄호인 경우이고, 체크 해둔 쌍에 있는 경우
    if is_bracket == ')' and check[pair[cur_idx]]:
        dfs(cur_idx + 1, depth)
    # 괄호를 지우지 않거나, 일반 문자열인 경우
    else:
        sub_value.append(is_bracket)
        dfs(cur_idx + 1, depth)
        sub_value.pop()


if __name__ == '__main__':
    string = list(stdin.readline().strip())
    stack = []
    check = [False for _ in range(len(string))]
    pair = [0 for _ in range(len(string))]
    answer = set()
    sub_value = []

    # 올바른 괄호끼리, 쌍이 되는 경우를 체크함
    for idx, bracket in enumerate(string):
        if bracket == '(':
            stack.append(idx)
        elif bracket == ')':
            pair[idx] = stack[-1]
            pair[stack[-1]] = idx
            stack.pop()

    dfs(0, len(string))

    # 출력 시 사전 순으로 정렬.
    print('\n'.join(sorted(answer)))