C++で通信塔のグループ数を求める方法｜DFSによる連結成分カウントの実装例

問題の概要

2次元のバイナリ行列が与えられます。各セルの値は次の意味を持ちます。

• 1 … そのセルに通信塔が存在する
• 0 … 空きセルである

通信塔同士は、以下のルールに従って互いに通信できます。

1. 塔Aと塔Bが同じ行または同じ列に配置されている場合、直接通信できます。
2. 塔Aが塔Bと通信でき、塔Bが塔Cと通信できるなら、塔Aは塔Cとも通信できます（推移律）。

この条件のもとで、互いに通信可能な塔の集合（グループ）の総数を求めます。これはグラフ理論でいう連結成分の数を数える問題にほかなりません。

入力例

この行列の場合、5つの塔すべてが行・列を介して相互に到達できるため、答えは 1 になります。

解法のアプローチ：DFS（深さ優先探索）

この問題は深さ優先探索（DFS）を使うと簡潔に解けます。考え方の基本は次のとおりです。

• まだ訪問していない塔（値が 1 のセル）を見つけたら、グループ数を 1 増やす。
• そのセルを出発点にDFSを実行し、同じ行・同じ列にある未訪問の塔をすべて再帰的に訪問する。
• 訪問済みのセルには 2 を代入し、二重カウントを防止する。

アルゴリズムの手順

1. 関数 dfs(matrix, i, j, n, m) を定義する。
2. matrix[i][j] = 2 として、現在のセルを訪問済みにする。
3. k を 1 から n-1 まで動かし、p = (i + k) mod n、q = j として同じ列上のセルを確認する。matrix[p][q] が 1 なら、そこからさらにDFSを再帰呼び出しする。
4. 同様に、k を 1 から m-1 まで動かし、p = i、q = (j + k) mod m として同じ行上のセルを確認し、必要なら再帰呼び出しする。
5. メイン処理では行列全体を走査し、値が 1 のセルが見つかるたびにカウンタ ans をインクリメントしてDFSを開始する。
6. 最後に ans を返す。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    void dfs(vector<vector<int>>& matrix, int i, int j, int& n, int& m) {
        matrix[i][j] = 2;
        for (int k = 1; k < n; k++) {
            int p = (i + k) % n, q = j;
            if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
        }
        for (int k = 1; k < m; k++) {
            int p = i, q = (j + k) % m;
            if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
        }
    }
    int solve(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    ans++;
                    dfs(matrix, i, j, n, m);
                }
            }
        }
        return ans;
    }
};

int solve(vector<vector<int>>& matrix) {
    return (new Solution())->solve(matrix);
}

main(){
    vector<vector<int>> v = {
        {1,1,0},
        {0,0,1},
        {1,0,1}
    };
    cout << solve(v);
}

入力

{{1,1,0},
{0,0,1},
{1,0,1}};

出力

1

計算量の目安

各セルは最大でも1回しか訪問されませんが、1回の訪問ごとに行方向・列方向の走査に O(n + m) の時間がかかるため、全体の計算量は O(n × m × (n + m)) となります。行列サイズが大きいケースでは、Union-Find（素集合データ構造）を使って行・列ごとに塔を統合していく方法の方が効率的になることもあるので、状況に応じて使い分けるとよいでしょう。