Pythonで点の集合を距離条件に基づいてグループ化するプログラムの作成方法

問題の概要

点のリストと整数 k が与えられたとします。各点は (x, y) の形式で表されるデカルト座標上の位置です。2つの点 p1 と p2 の間のユークリッド距離が k 以下である場合、その2点は同じグループに属するとみなせます。このとき、全体をいくつの互いに素な（重なり合わない）グループに分割できるか、その総数を求めるのが目的です。

入力例

たとえば、次のような入力を考えます。

• points = [[2, 2], [3, 3], [4, 4], [11, 11], [12, 12]]
• k = 2

この場合、出力は 2 になります。理由は、点を次の2つのグループに分けられるためです。

• グループ1：[2,2], [3,3], [4,4]
• グループ2：[11,11], [12,12]

解き方のアプローチ

この問題は、グラフ理論における連結成分（Connected Components）の数え方と考えることができます。距離が k 以内の点同士を「辺」で結んだグラフを作り、その連結成分の個数を DFS（深さ優先探索）で数えます。

アルゴリズムの手順

1. dfs() 関数を定義します。引数としてインデックス i を受け取ります。
2. i がすでに訪問済みセット seen に含まれていれば、そのまま return します。
3. i を seen に追加します。
4. 隣接リスト adj[i] 内の各ノード nb に対して、再帰的に dfs(nb) を呼び出します。
5. メイン処理では以下を行います。
   • adj：隣接リスト（マップ）を初期化します。
   • n：点の総数を取得します。
   • すべての点のペア (i, j) について、p1 = points[i]、p2 = points[j] のユークリッド距離が k 以下であれば、adj[i] に j を、adj[j] に i を追加します。
   • seen：新しい空のセットを用意します。
   • ans：0 で初期化します。
   • 各インデックス i について、まだ訪問していなければ ans を +1 し、dfs(i) を実行します。
6. 最後に ans を返します。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

from collections import defaultdict
class Solution:
   def solve(self, points, k):
      adj = defaultdict(list)

      n = len(points)
      for j in range(n):
         for i in range(j):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= k ** 2:
               adj[i].append(j)
               adj[j].append(i)

      seen = set()
      def dfs(i):
         if i in seen:
            return
         seen.add(i)
         for nb in adj[i]:
            dfs(nb)

      ans = 0
      for i in range(n):
         if i not in seen:
            ans += 1
            dfs(i)
      return ans
ob = Solution()
points = [
[2, 2],
[3, 3],
[4, 4],
[11, 11],
[12, 12]
]
k = 2
print(ob.solve(points, k))

入力

[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]],2

出力

2

計算量について

すべての点のペアを比較してグラフを構築するため、時間計算量は O(n²) となります。また、隣接リストの保存にも最大 O(n²) のメモリが必要です。点の数が少ない・中程度の場合には十分実用的ですが、点数が非常に多い場合は Union-Find（素集合データ構造）などを活用した最適化も検討するとよいでしょう。