T - 2.03.多次元配列

Time Limit: 0 msec / Memory Limit: 0 KB

前のページ | 次のページ

キーポイント

  • 2次元配列は2次元の表を扱うときに便利
  • vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値))で宣言できる
  • 初期値は省略可能
  • 変数名.at(i).at(j)でi行目j列目へアクセスできる
  • 変数名.size()で縦の大きさを取得できる
  • 変数名.at(0).size()で横の大きさを取得できる
  • 要素を指定して初期化する例
vector<vector<int>> data = {
  {7, 4, 0, 8},
  {2, 0, 3, 5},
  {6, 1, 7, 0},
};
  • 2次元以上の配列を多次元配列という
  • vectorをN個入れ子にしたものをN次元配列という

配列は「データの列」を扱うための機能でした。
このページでは「データの表」を扱うときに便利な 2次元配列、さらに高次元の 多次元配列 と呼ばれる配列を紹介します。

2次元配列

次の問題を見てみましょう。

例題

縦3行、横4列の整数が書かれた表があります。この表に何個の0が含まれているかを求めてください。

表の例を次に示します。

7 4 0 8
2 0 3 5
6 1 7 0
入力
7 4 0 8
2 0 3 5
6 1 7 0
実行結果
3

このようなデータの表を2次元配列で扱うときは次のように書けます。

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

int main() {

  // int型の2次元配列(3×4要素の)の宣言
  vector<vector<int>> data(3, vector<int>(4));

  // 入力 (2重ループを用いる)
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
      cin >> data.at(i).at(j);
    }
  }

  // 0の個数を数える
  int count = 0;

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {

      // 上からi番目、左からj番目の画素が0かを判定
      if (data.at(i).at(j) == 0) {
        count++;
      }

    }
  }

   cout << count << endl;

}

宣言

2次元配列の宣言は次の形式になります。

vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値));
vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2));  // 初期値を省略

初期値は省略することができます。省略した場合は「要素の型」に対応するゼロ値で初期化されます。
例えば要素の型がintなら、初期値は0で、stringなら空文字列("")です。

表のようなデータを扱う場合、一般的には次のようにします。

vector<vector<要素の型>> 変数名(縦の要素数, vector<要素の型>(横の要素数));

例題で扱ったデータは、

  • 要素が整数
  • 縦に3行
  • 横に4列

の表であるため、次のように宣言しています。

vector<vector<int>> data(3, vector<int>(4));

アクセス

2次元配列の要素にアクセスする場合は次のように書きます。

変数名.at(添字1).at(添字2)

宣言時にvector<vector<要素の型>> 変数名(縦の要素数, vector<型>(横の要素数))としている場合、より具体的には次のようになります。

変数名.at(上から何番目か).at(左から何番目か)

例題では、入力の部分で「上からi番目、左からj番目」の要素に入力するため、

cin >> data.at(i).at(j)

と書いています。
また、上からi番目、左からj番目のマスが0かどうかを判定するため、

if (data.at(i).at(j) == 0)

と書いています。

大きさの取得

vector<vector<int>> data(3, vector<int>(4));

data.size();  // 3 (縦の要素数) (12ではないことに注意!)
data.at(0).size();  // 4 (横の要素数)

縦の要素数を取得するには変数名.size()として、横の要素数を取得するには変数名.at(0).size()とします。

変数名.size()とした時に、すべての要素の個数ではなく縦の要素数が返ってくることに注意してください。
すべての要素数が必要なときは縦の要素数 * 横の要素数で求める必要があります。

2次元配列の考え方

説明のために、これまで扱ってきた通常の配列を"1次元配列"と呼ぶことにします。

ここで、1次元配列の復習をします。"要素数"個の"初期値"からなる配列は次のように宣言しました。(1.13 配列の細かい話を参照)

vector<要素の型> 変数名(要素数, 初期値);

2次元配列は「"1次元配列"の配列」と考えると分かりやすいと思います。

2次元配列の宣言の考え方

1次元配列を表す型はvector<要素の型>でした。
2次元配列を表す型は、「"1次元配列"の配列」なのでvector<vector<要素の型>>となります。("外側の配列の要素の型"が1次元配列を表す型になっています。)
また、2次元配列の"初期値"は"1次元配列"なのでvector<vector<要素の型>> 変数名(要素数1, 初期値)の"初期値"の部分にはvector<要素の型>(要素数2))を指定します。("要素数2"個の要素から成る1次元配列です。)

要素へのアクセスは次のように考えられます。

変数名.at(i)  // i番目の1次元配列
変数名.at(i).at(j)  // i番目の1次元配列 のj番目の要素

2次元配列の添字を「上から何番目か」と「左から何番目か」で表すことが直感的に感じられない人もいると思いますが、慣れましょう。たて×よこ と覚えると良いです。
例題の入力と配列の添字は次の表のように対応しています

i\j 0 1 2 3
0 7 4 0 8
1 2 0 3 5
2 6 1 7 0

このデータが入力されたとき、以下の要素が何になっているかを考えてみてください。

  • data.at(0).at(1)
  • data.at(1).at(3)
  • data.at(2).at(2)

答え

  • data.at(0).at(1)4 (0番目の1次元配列 の1番目の要素)
    0番目の1次元配列は {7, 4, 0, 8} です。

  • data.at(1).at(3)5 (1番目の1次元配列 の3番目の要素)
    1番目の1次元配列は {2, 0, 3, 5} です。

  • data.at(2).at(2)7 (2番目の1次元配列 の2番目の要素)
    2番目の1次元配列は {6, 1, 7, 0} です。


多次元配列

2次元配列をさらに拡張して、3次元配列や4次元配列といったより高次元の配列を作ることもできます。
1次元より次元の大きい配列をまとめて多次元配列と呼びます。

3次元配列を使った例を見てみましょう。

例題

まるばつゲームの状態がN個与えられます。マルは'o'、バツは'x'、空白は'-'で表されます。すべての状態の'o'の個数の和を求めてください。

1つ目の状態

- - -
- x -
- o -

2つ目の状態

x o -
- o -
x - -
入力
2
- - -
- x -
- o -

x o -
- o -
x - -
実行結果
3
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  // N × (3 × 3)要素の配列を宣言
  vector<vector<vector<char>>> data(N, vector<vector<char>>(3, vector<char>(3)));

  // 入力
  for (int i = 0; i < N; i++) {
    // i番目の状態を読む
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        cin >> data.at(i).at(j).at(k);
      }
    }
  }

  // 'o'の数を数える
  int count = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {

        // 「i番目の状態」「上からj番目」「左からk番目」の要素が'o'か判定
        if (data.at(i).at(j).at(k) == 'o') {
          count++;
        }

      }
    }
  }

   cout << count << endl;
}

3次元以上の配列も2次元配列とほとんど変わりません。

宣言

3次元配列の場合の宣言方法を次に示します。

vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));
vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3)));  // 初期値を省略

ギョッとしてしまうかもしれませんが、基本的な考え方は2次元配列のときと同じです。
3次元配列を「"2次元配列"の配列」つまり「"1次元配列の配列"の配列」と考えます。分かりやすくするために改行を入れてみます。

vector<
  vector<vector<要素の型>> /* 2次元配列の型 */
> 変数名(要素数1,
  vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)) /* 2次元配列の値 */
);

4次元以上の場合も同様に宣言します。N次元配列を「"N-1次元配列"の配列」と考えましょう。

アクセス

N次元配列の要素にアクセスするには次のように書きます。

変数名.at(添字1).at(添字2).at(添字3) ... .at(添字N)

.at(添字)をN回繰り返します。


注意点

多次元配列を扱う際の基本的な注意点は1次元配列と同様です。

多次元配列ではさらに、添字の順番に注意しましょう。
また、変数名.size()では1次元目の要素数が取得できますが、すべての要素の個数が取得できる訳ではないという点に注意しましょう。

vector<vector<vector<int>>> data = {
  {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
  },
  {
    {13, 14, 15, 16},
    {17, 18, 19, 20},
    {21, 22, 23, 24},
  },
};

int size1 = data.size();
cout << size1 << endl;  // 2

int size2 = data.at(0).size();
cout << size2 << endl;  // 3

int size3 = data.at(0).at(0).size();
cout << size3 << endl;  // 4

cout << size1 * size2 * size3 << endl;  // 24

細かい話

要素を指定して初期化する

// 2次元配列の初期化
vector<vector<int>> data1 = {
  {7, 4, 0, 8},
  {2, 0, 3, 5},
  {6, 1, 7, 0}
};

// 3次元配列の初期化
vector<vector<vector<char>>> data2 = {
  {
    {'-', '-', '-'},
    {'-', 'x', '-'},
    {'-', 'o', '-'}
  },
  {
    {'x', 'o', '-'},
    {'-', 'o', '-'},
    {'x', '-', '-'}
  }
};

あらかじめ要素の値とサイズが決まっている場合に、要素を指定して初期化することができます。

1次元の配列を多次元配列として使う

「データの表」を扱いたいときは多次元配列が適していることを紹介しました。しかし「データの表」は一列に"ならす"ことで「データの列」として見ることができるので、1次元の配列で扱うこともできます。

2次元の表を1次元に変換する方法はいろいろ考えられますが、表を行ごとに分割して「1列目のデータ→2列目のデータ→3列目のデータ→...」という1次元の列に変換するのがシンプルです。
例えば縦H行、横W列の表を扱いたい時、データの個数はH×W個なので、vector<型> 変数名(H * W);と表現することができます。この場合、上からy個目、左からx個目の要素にアクセスするときは変数名.at(y * W + x)とします。

y * Wの部分は、目的要素のある行の先頭の位置を表しています。一行のデータは並んでいるので、x列目のデータを得るには、行の先頭からxだけ進んだ位置にあるというわけです。

(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)

N×0の二次元配列

後から配列に要素を追加して使う場合などに、N×0の配列を宣言することがあります。

以下のように書くと、N×0の二次元配列になります。

vector<vector<型>> 変数名(N);  // 「要素数0の配列」の配列

外側のvectorの初期値を省略することで、N個の配列の要素数はそれぞれ0になります。

vector以外を用いた多次元配列

「1.13配列」の細かい話でも紹介しましたが、C++にはvector以外にも配列を表現する方法があります。

vector<int> data(3); // vectorによる要素数3の配列
int data[3]; // Cの要素数3の配列
array<int, 3> data; // arrayによる要素数3の配列

このページではvectorを使った多次元配列を紹介しましたが、vector以外の配列で多次元配列を表現することもできます。

// vector を用いた2次元配列
vector<vector<int>> data(3, vector<int>(4));  // 縦3 x 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス (1番目から数えていることに注意)

// array を用いた2次元配列
array<array<int, 4>, 3> data = {};  // 縦3 × 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス

// Cの配列を用いた2次元配列
int data[3][4] = {};  // 縦3 × 横4 の2次元配列
data[1][2]  // 上から2番目、左から3番目の要素へのアクセス

arrayやCの配列は要素数に変数を用いることができなかったり、Cの配列では範囲外アクセスをしてもエラーにならずにバグを埋め込んでしまうという点に注意する必要があります。慣れるまではvectorの多次元配列を使うようにしましょう。


問題

リンク先の問題を解いてください。

ABCの問題

ここまでの知識で解ける問題をAtCoder Beginner Contestの過去問題から紹介します。練習問題だけでは物足りない人は挑戦してみてください。