002 - Encyclopedia of Parentheses（★3）の解説

何の話かと言うと

atcoder.jp

上記の問題をネタにキューを使った再起処理の基本を説明します。

キューを使った再起処理

公式解説では、 通りのすべての組み合わせから条件に合うものを抽出する方法が説明されていますが、再帰処理を用いて条件に合うものだけを生成することもそれほど難しくありません。

まず、簡単のために、条件を考えずに 通りのすべての組み合わせを生成してみます。

n 文字目まで用意したら、その後ろには "(" をつけるか ")" を付けるかの2択で n+1 文字目を生成すればよいので、次の様な実装ができます。

from collections import defaultdict, deque

def braket(N):
  q = deque()
  q.append('(')
  q.append(')')
  while q:
    s = q.popleft()
    if len(s) == N:
      print(s)
      continue
    q.append(s + '(')
    q.append(s + ')')

braket(4)

今の場合、"(" を先にキューに追加しているので、"(" < ")" とした辞書順に生成されます。

((((
((()
(()(
(())
()((
()()
())(
()))
)(((
)(()
)()(
)())
))((
))()
)))(
))))

ちなみに、popleft() で取り出すところを pop() で取り出すと生成順序が逆向きになります。

条件に合うものだけを生成する

条件に合うものだけを生成するには、"(" と ")" を何個使ったかをカウントする必要があります。キューから文字列を取り出して、毎回、カウントするのは非効率なので、カウント数も含めてキューに入れてしまいます。すると、こんな感じで実装できます。

from collections import defaultdict, deque

def braket(N):
  bra = N // 2
  ket = N // 2
  q = deque()
  q.append((bra-1, ket, '(')) # bra, ket, string
  while q:
    bra, ket, s = q.popleft()
    if bra == 0 and ket == 0:
      print(s)
      continue
    if bra > 0:
      q.append((bra-1, ket, s + '('))
    if bra < ket:
      q.append((bra, ket-1, s + ')'))

braket(6)

結果はこちらで、意図通りに出力されていますね。よかった！

((()))
(()())
(())()
()(())
()()()

atcoder.jp