C++で花壇に花を植えられるか判定するアルゴリズムを解説

問題概要

細長い花壇があるとします。一部の区画にはすでに花が植えられており、残りの区画は空いています。ここで重要な制約がひとつあります。それは「花を隣接する区画に植えてはならない」というルールです。隣り合った花は水分を奪い合い、どちらも枯れてしまうためです。

花壇は 0 と 1 からなる配列で表現され、0 は空き区画、1 は花が植えられている区画を意味します。さらに整数 n が与えられたとき、この隣接禁止ルールを破ることなく新しい花を n 本すべて植えられるかどうかを判定します。

たとえば、入力が flowerbed = [1,0,0,0,1]、n = 1 の場合、出力は True（真）となります。

解法のアプローチ

この問題は貪欲法（グリーディ法）で効率よく解けます。配列を左から右へ走査し、植えられる場所があればその場で花を植えていくシンプルな戦略です。具体的には以下の手順に従います。

1. 花壇のサイズが n より小さい場合は false を返します。
2. 花壇のサイズが 1 で、flowerbed[0] が 0、かつ n が 1 の場合は true を返します。
3. i を 0 から花壇のサイズ未満まで 1 ずつ増やしながら、以下の処理を繰り返します。
   • n > 0 の場合、次のように場合分けします。
     • i が先頭（0）のとき： flowerbed[i] が 0 かつ flowerbed[1] が 0 であれば、flowerbed[0] を 1 に更新し、n を 1 減らします。
     • i が末尾（サイズ − 1）のとき： flowerbed[i] が 0 かつ flowerbed[i − 1] が 1 でなければ、flowerbed[i] を 1 に更新し、n を 1 減らします。
     • それ以外のとき： flowerbed[i]、flowerbed[i + 1]、flowerbed[i − 1] の 3 つすべてが 0 であれば、flowerbed[i] を 1 に更新し、n を 1 減らします。
   • 処理の途中で n が 0 になったら、ただちに true を返します。
4. ループ完了後も n が 0 であれば true を返し、それ以外は false を返します。

実装上のポイントは、両端の区画では片側だけを確認すればよい一方で、中央の区画では左右両隣が空いていることを確認する必要がある点です。

C++での実装例

理解を深めるために、以下の実装コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canPlaceFlowers(vector<int>& flowerbed, int n) {
      if (flowerbed.size() < n)
         return false;
      if (flowerbed.size() == 1 && flowerbed[0] == 0 && n == 1)
         return true;
      for (int i = 0; i < flowerbed.size(); i++) {
         if (n > 0) {
            if (i == 0) {
               if (flowerbed[i] == 0 && flowerbed[1] == 0) {
                  flowerbed[0] = 1;
                  n--;
               }
            }
            else if (i == flowerbed.size() - 1) {
               if (flowerbed[i] == 0 && flowerbed[i - 1] != 1) {
                  flowerbed[i] = 1;
                  n--;
               }
            }
            else if (flowerbed[i] == 0 && flowerbed[i + 1] == 0 && flowerbed[i - 1] == 0) {
               flowerbed[i] = 1;
               n--;
            }
         }
         if (n == 0) {
            return true;
         }
      }
      if (n == 0) {
         return true;
      }
      return false;
  }
};
main(){
   Solution ob;
   vector<int> v = {1,0,0,0,1};
   cout << (ob.canPlaceFlowers(v, 1));
}

入力

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

出力

1

計算量の評価

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(m)（m は花壇の区画数）です。また、花壇の配列自体を直接書き換えることで追加のメモリをほとんど使わず、空間計算量は O(1) に抑えられます。隣接チェックを避けるための追加配列が不要になる点も、この手法の大きなメリットといえるでしょう。