【C#】深さ優先探索の実装 AtCoder Beginner Contest 029

今回は深さ優先探索の実装をしてみました。AtCoderでちょうど良いテーマがあったので、それを解いてみました。

atcoder.jp

深さ優先探索

例のごとく、細かい説明はWikipediaを参照で。 ja.wikipedia.org

AtCoderの問題

結果

コード

github.com

条件

今回与えられている条件は以下。

1. 1行目にパスワードの長さN(1<=N<=8)が与えられる
2. a, b, c 以外の文字は含まれない。

考え方

深さ優先探索は、主に”再帰あり”と”再帰なし”の解き方に分けられます。今回は再帰ありで実装しました。まず、ベースとなる考え方ですが、与えられたNは木の深さとして使用します。

イメージとしてはこんな感じです。今回はa,b,cしか使ってないので、aを根とする木、bを根とする木、cを根とする木を作成します。前の状態を引数として再帰的に関数を呼び出します。その処理の中でまたa,b,cを結合しています。木の深さNを引数として渡しておき、これが0になるまで処理を繰り返します。

そして、一番下のノードまで結合した時点でNは0になっているので処理を終了し、それまでに結合し続けていた文字列を出力します。

static void brute(int n, string r)
{
    if (n == 0)
    {
        Console.WriteLine(r);
        return;
    }
    brute(n - 1, r + 'a');
    brute(n - 1, r + 'b');
    brute(n - 1, r + 'c');
}

まとめ

すごくシンプルに実装できるので、あまり考察などは必要なく、深さ優先探索の勉強テーマにはちょうど良いかと思います。

再帰処理のイメージが苦手な人は、処理を実行する主体がノードで、その子ノード分を再帰的に処理を実行していると考えるとわかりやすい気がします。特に、文字列の情報を持ち、その文字列に結合していくイメージは想像しやすいかと。