競プロ典型90問 002 - Encyclopedia of Parentheses（★3）のDFS解法を解説

今回は「競技プログラミングの鉄則」などの著書を出されているE869120(https://twitter.com/e869120)さんが企画・作成した競プロ典型90問(https://atcoder.jp/contests/typical90)の002 - Encyclopedia of Parentheses（★3）のDFSを使った解法を説明していこうと思います。

https://amzn.to/3XrvjFF

問題概要

https://atcoder.jp/contests/typical90/tasks/typical90_b

この問題は下記の条件を満たすものを正しいカッコ列とした時に正しいカッコ列を全て辞書順で出力するという問題です。

• () は正しいカッコ列である

• Sが正しいカッコ列であるとき、文字列(+S+)は正しいカッコ列である

• S,Tが正しいカッコ列であるとき、文字列S+Tは正しいカッコ列である

• それ以外の文字列はすべて、正しいカッコ列でない

https://atcoder.jp/contests/typical90/tasks/typical90_b

1≤N≤20と小さいため全ての候補を探索した上で、それぞれが正しいカッコ列であるか判定するという方法が考えられます。

想定解法はbit全探索を使って0を開きカッコ、1を閉じカッコとして全ての候補を生成しています。

私はこの解法は思いつきませんでしたが、全ての候補をDFS(深さ優先探索)を使って列挙できると考えました。

DFSを使った解法

まず解法のコードは下記になります。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 与えられた文字列が正しい文字列かどうかを判定する
bool ok(string val) {
  // カッコの変化を表す
  ll diff = 0;
  for(auto x: val) {
    // 開きカッコの時diffを増やして、そうでないとき減らす
    if (x == '(') diff++;
    else diff--;
    // この時点でdiffがマイナスになってしまったら、閉じカッコの方が多いので正しい文字列ではない
    if (diff < 0) return false;
  }
  // 最後まで到達した時に開きカッコと閉じカッコの数が同じかどうか
  return diff == 0;
}

ll N;
// 再帰的に呼び出される関数
void dfs(string val) {
  // 文字列のサイズがNになったら判定を行う
  if (N == val.size()) {
    if (ok(val)) cout << val << endl;
    return;
  }
  // ここで開きカッコの方から呼び出すことで文字列を辞書順に探索することができる
  // 例えばN=2の時、最初に判定が行われる文字は"(("となる
  // 次に判定が行われる文字は"()"となる
  // 次に判定が行われる文字は")("となる
  // 最後に"(("の判定が行われ、正しい文字列は"()"のみであるとわかる
  dfs(val + '(');
  dfs(val + ')');
}

int main() {
  cin >> N;
  dfs("");
  return 0;
}

コメントをみるとある程度理解できるかと思いますが、まずmain関数から空文字列を引数にdfsの関数を呼び出し、開きカッコか閉じカッコの文字を今の値に追加して再帰的にdfs関数を呼び出します。

そしてdfsの引数にある文字がN文字になった時点で正しい文字列かどうか判定し、正しい場合はそれを出力して、探索を打ち切ります。

計算量はdfsの関数内で毎回2回関数が呼び出されるため、O(2^N)となります。

制約の最大値であるN=20の場合には、2^20=1048576となり十分間に合います。

この問題ではあえてDFSで利点はありませんが、例えば「a,b,cの3文字を使った長さNの文字列を列挙せよ」という問題が出た時に再帰的に呼び出すdfsの呼び方を下記のようにすることで辞書順で簡単に列挙することができます。

dfs(val + 'a');
dfs(val + 'b');
dfs(val + 'c');

このように応用が効くので覚えておいて損はないかと思います。

N=2で呼び出した時このような値を順番に得られる