Pythonでポイントのセットをk個の異なるグループにグループ化するプログラム

ポイントのリストと数kがあるとします。ポイントは、デカルト座標を表す（x、y）の形式です。 2点p1とp2の間のユークリッド距離が<=kの場合、それらをグループ化できます。互いに素なグループの総数を見つける必要があります。

したがって、入力がpoints =[[2、2]、[3、3]、[4、4]、[11、11]、[12、12]]、k =2の場合、出力は次のようになります。 2、2つのグループを作成できるため：（[2,2]、[3,3]、[4,4]）と（[11,11]、[12,12]）

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これには私がかかります

• 私が見られている場合、

  • 戻る

  • 見たにiを挿入

  • adj [i]のnbごとに、実行

    • dfs（nb）

    • メインの方法から、次のようにします-

    • adj：=マップ

    • n：=ポイントのサイズ

    • 0からnの範囲のjについては、次のようにします

      • 0からjの範囲のiの場合、実行

        • p1：=ポイント[i]

        • p2：=ポイント[j]

        • p1とp2の間のユークリッド距離が

          • adj [i]

            の最後にjを挿入します

          • adj [j]

            の最後にiを挿入します

    • 見た：=新しいセット

    • ans：=0

    • 0からnの範囲のiの場合、実行

      • 見なかったら

        • ans：=ans + 1

        • dfs（i）

    • ansを返す

理解を深めるために、次の実装を見てみましょう-

例

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