파이썬, 유효한 괄호쌍 출력하기 (백트래킹)

파이썬, 유효한 괄호쌍 출력하기 (백트래킹)

 

글. 오상문 sualchi@daum.net 

 

올바른 괄호쌍을 출력하는 예제입니다. 

예를 들어 괄호 3쌍일 때 올바른 괄호쌍 경우는 5가지입니다.

 {{{}}}
 {{}{}}
 {{}}{}
 {}{{}}
 {}{}{}

 

예제 코드는 다음과 같습니다.

data = []
count = 0

def solution(n, Open, Close, s):
  global count

  # 열린것과 닫힌 것이 같으면
  if Open==n and Close==n:
    data.append(s) # 괄호쌍 문자열 추가, 종료
    count += 1
    return

 

  # 아래에서 유효한 경우만 진행하므로
  # 다른 종료 검사는 필요없음

 

  # 백트래킹, 유효하지 않은 경우는 가지치기
  if Open < n: # 열린 것이 n보다 작으면
    solution(n, Open+1, Close, s+'{')
  if Open > Close: # 열린게 닫힌 것보다 많으면
    solution(n, Open, Close+1, s+'}')

 

# --------- main -----------------

N = int(input())
solution(N, 0, 0, "")

 

print(count, '개')
for s in data:
  print(s)

<이상>