処理の途中で安直に配列内の要素を書き換えてはいけない

アルゴリズム実技検定のE問題で初歩的なミスをしたので、今後同じようなミスをしないようにメモをしておきます。内容はタイトル通りです。

1.問題

E – SNSのログ

グラフ問題です。ただし、3種類の操作があるので、それぞれをちゃんと実装しなければなりません。

2.やらかした点

次のようなコードを提出しました。

問題となったのは次の部分。

rep(i, n) {
        if (follow[user][i]) {
          rep(j, n) {
            if (follow[i][j]) {
              cout << "i=" << i << ",j=" << j << endl;
              follow[user][j] = true;
            }
          }
        }
      }

これは、操作のフォローフォローを実装しようとしたものです。”ある人がフォローしている人"がフォローしている人をフォローするという、友達の友達は友達と言った操作です。

さて、この実装で動かすと良さそうに見えます。しかし、正常には2と5(二次元配列では1と4)の場合のみif文が実行されるはずなのに、3(二次元配列では2)も通るようになります。

3.なにが駄目だったか

上の実装では、誰かがフォローしている人をフォローするたびに二次元配列の要素を書き換えています。このため、2(2次元配列では1)は3(二次元配列では2)をフォローしているので、2がフォローしている人をフォローした時、二次元配列が次のように書き換えられます。

follow[0][2] = false -> follow[0][2] = true

すると、外側のループでiがインクリメントされた時、次は1が3をフォローしているかという判定がされ、先程フォローしたことになったので、if文内の処理に移ります。

毎回要素を書き換えてしまうので、操作前はフォローしてなかった人も操作の途中でフォローしてしまい、本来処理しない人の分まで処理してしまっています。

4.ACしたコード

結局次のように実装するとACできました。該当部分だけでなく、フォロー返しの部分も実装を変更しています。

操作前に、該当ユーザがフォローしている人を予め抽出しておき、その抽出したユーザに対してのみ処理を行うようにしています。

5.結論

処理の途中で安直に配列内の要素を書き換えてはいけない。