C++で行列がバイナリ行列（二値行列）かどうかを判定するプログラム

バイナリ行列とは？

バイナリ行列（Binary Matrix）とは、構成するすべての要素が 0 または 1 のいずれかである行列のことです。ブール行列（Boolean Matrix）、関係行列（Relational Matrix）、論理行列（Logical Matrix）と呼ばれることもあります。

以下に例を示します。

$$\begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ \end {bmatrix}\:\:\:\:\:\:\:\:\: \begin{bmatrix} 0 & 3 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 2 \\ \end{bmatrix}\\\tiny This\:is\:a\:Binary\:Matrix\:\:\:\:\:\:\:\: This\:is\:not\:a\:binary\:matrix$$

上図の左側の行列は、すべての要素が 0 か 1 なのでバイナリ行列です。一方、右側の行列には 3 や 2 といった 0・1 以外の値が含まれているため、バイナリ行列ではありません。

入出力例

Input: m[4][3] = { { 0, 0, 0, 0 },
   { 1, 1, 1, 1 },
   { 1, 1, 0, 0 } }
Output: its a binary matrix

アプローチ

この問題は非常にシンプルです。行列全体を走査し、すべての要素が 0 または 1 であれば「バイナリ行列である」と出力し、ひとつでもそれ以外の値が見つかれば「バイナリ行列ではない」と出力します。計算量は行数を R、列数を C とすると O(R × C) となります。

アルゴリズム

Start
Step 1 -> マクロとして #define row 3 と #define col 4 を定義する
Step 2 -> 行列がバイナリ行列かどうかを判定する関数を宣言する
   bool check(int arr[][col])
      Loop For int i = 0 and i < row and i++
         Loop For int j = 0 and j < col and j++
            IF(!(arr[i][j] == 0 || arr[i][j] == 1))
               return false
            End
         End
      End
   return true
Step 3 -> main() 内で
   配列を宣言する：int arr[row][col] = { { 0, 0, 0, 0 },
      { 1, 1, 1, 1 },
      { 1, 1, 0, 0 } }
   If (check(arr))
      「its a binary matrix」と出力する
   Else
      「its not a binary matrix」と出力する
Stop

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 4
// 行列がバイナリ行列かどうかを判定する関数
bool check(int arr[][col]){
   for (int i = 0; i < row; i++){
      for (int j = 0; j < col; j++){
         if (!(arr[i][j] == 0 || arr[i][j] == 1))
            return false;
      }
   }
   return true;
}
int main(){
   int arr[row][col] = { { 0, 0, 0, 0 },
      { 1, 1, 1, 1 },
      { 1, 1, 0, 0 } };
   if (check(arr))
      cout << "its a binary matrix";
   else
      cout << "its not a binary matrix";
   return 0;
}

実行結果

its a binary matrix

コードの解説

関数 check() では、二重の for ループを使って行列の全要素を順番に調べています。要素が 0 でも 1 でもない場合は、その時点で false を返して処理を終了するため、無駄な走査を行いません。すべての要素が 0 か 1 であればループを抜けて true を返し、main 関数側でその結果に応じてメッセージを出力します。