Pythonでブーメラン（等距離点タプル）の数を数えるアルゴリズムと実装

問題の概要

平面上に互いに異なる n 個の点が与えられているとします。ここで「ブーメラン」とは、点のタプル (i, j, k) のうち、i と j の距離が i と k の距離と等しいものを指します。この問題では、与えられた点集合の中にブーメランがいくつ存在するかを求めます。

例えば、入力が [[0,0],[1,0],[2,0]] の場合、出力は 2 になります。これは、[[1,0],[0,0],[2,0]] と [[1,0],[2,0],[0,0]] という2つのブーメランが存在するためです。頂点となる点 [1,0] から見て、残りの2点までの距離が等しいので、順序の異なる2通りの組み合わせが成立します。

解法のアプローチ

この問題は、各点を頂点としたときの「他の点までの距離の出現回数」をハッシュマップで集計することで効率よく解けます。手順は以下の通りです。

1. ブーメランのカウンタ counter_of_boomerangs を 0 で初期化します。
2. 配列内の各点 point_1 について以下を繰り返します。
   • x1, y1 に point_1 の座標を代入します。
   • 距離ごとの出現回数を記録する辞書 distance_count_dict を用意します。
   • 配列内の各点 point_2 について、x 座標の差と y 座標の差の二乗和（ユークリッド距離の二乗）を計算し、その値をキーとして辞書のカウントを1増やします。
   • すべての点との距離を集計した後、辞書内の各距離 d について、同じ距離を持つ点の数 n を取り出し、n × (n − 1) をカウンタに加算します。
3. 最終的な counter_of_boomerangs を返します。

なぜ n × (n − 1) なのか？

ある頂点 i から等距離にある点が n 個ある場合、その中から順序付きペア (j, k) を選ぶ方法は n × (n − 1) 通りあります。(i, j, k) と (i, k, j) は別々のブーメランとして数えられる点に注意しましょう。また、平方根を取らずに「距離の二乗」をキーとして使うことで、浮動小数点誤差を避けながら高速に処理できるのもポイントです。

実装例

それでは、実際のPythonコードを見てみましょう。

from collections import defaultdict
class Solution:
    def numberOfBoomerangs(self, points):
        counter_of_boomerangs = 0
        for point_1 in points:
            x1, y1 = point_1
            distance_count_dict = defaultdict(int)
            for point_2 in points:
                x2, y2 = point_2
                diff_x = x2 - x1
                diff_y = y2 - y1
                dist = diff_x ** 2 + diff_y ** 2
                distance_count_dict[dist] += 1
            for d in distance_count_dict:
                n = distance_count_dict[d]
                counter_of_boomerangs += n * (n - 1)
        return counter_of_boomerangs

ob = Solution()
print(ob.numberOfBoomerangs([[0,0],[1,0],[2,0]]))

collections.defaultdict(int) を使うことで、まだ登録されていない距離キーにアクセスした際も自動的に 0 で初期化されるため、コードを簡潔に保てます。

入力例

[[0,0],[1,0],[2,0]]

出力

2

計算量の目安

全ての点のペアについて距離を計算するため、時間計算量は O(n²) となります。一方、各イテレーションで保持する辞書のサイズは最大 n 個なので、空間計算量は O(n) です。