【AtCoder】【C#】グラフ問題でのノード同士の接続状態の管理、経路問題での通過したノードを管理する方法の紹介

今回のタイトルですが、題材となっているのは下記の問題です。

atcoder.jp

この問題では、

• グラフ問題において、ノード同士の接続情報がインプットで渡される

• 一度通過した経路を管理しなければいけない

といった特徴があります。AtCoderではこれ以外にも似たような問題が出てくることがあります。

今回の記事では、この2パターンについて、どのように実装すればいいか紹介します。これでパターン化して、次回以降実装に悩まなくて良くなれば良いなあと。

はじめに

ここでは、本題に入るために必要な情報を説明します。

問題へのリンク

記事の最初に貼っているリンクがまさにそれです。

問題の概要

• ノードとそれらがどのように接続されているかの情報があたえられます
• そのすべてのノードを1度だけ通る経路が何通りあるか調べてその数を解答します

前提とする知識

今回、DFSで実装していますがこの実装については説明しません。

本題

問題の解法

まずは、今回の問題の解法を説明します。

今回、始点がノード1からだと決まっているので、まずは1から見ていきます。1に繋がっているかつまだ訪れたことのないノードがあったとき、そのノード(2とします)を通過済みステータスに変更したうえで、2に接続していてかつ通過したことのないノードがあるか調査します。

これを最後まで繰り返して終点ノードまで到達してかつ全てのノードを通過していた場合に事前に定義したカウンターに1をプラスします。

やりたいこと

今回の問題では、以下2つの情報を管理する必要があります。

1. 各ノード同士が接続されているかどうかの情報
2. 各ノードが一度でも通ったかどうかの情報

1.は入力で与えられます。2.は問題の性質上、管理しないとすべてのノードを1度だけ通過するという制約への対応ができません。これらをどのように実装するかがポイントです。

方針について

方針としては、bool型の二次元配列を作成して表のような形で管理します。例として、下記の様なグラフが与えられたとします。

これを下記のように管理します。Tが接続シている状態、Fが接続していない状態です。

こうすることで、簡単に二次元配列のみで実装できます。

下記は実装例で、Nがノード数、Mが辺数、input[0]-1, input[1]-1 が各ノード番号を配列の添字の形に直したものです。

graph = new bool[N, N];
for (int i = 0; i < M; i++)
{
    input = Console.ReadLine().Split().Select(int.Parse).ToArray();
    graph[input[0] - 1, input[1] - 1] = true;
    graph[input[1] - 1, input[0] - 1] = true;
}

同様にノードを通過したかどうかも同様にbool型の配列で管理します。

bool[] visited = new bool[N];
visited[0] = true;

そして、全てを通過したかどうかはbool型の変数で管理します。

bool all_visited = true;

上記からわかるように、状態を管理したいときにbool型の配列・変数を使用して管理するのはよくある実装方法だと感じます。そのため、今回のケース以外にも汎用的に使えるのではないかなと思います。

実装

実装のリンクを貼ります

github.com