โปรแกรมจัดกลุ่มจุดเป็น K กลุ่มตามระยะทางยุคลิดใน Python

สมมติว่าเรามีรายการจุด (x, y) และตัวเลข k สามารถจัดกลุ่มจุด p1, p2 ได้หากระยะทางยุคลิดระหว่างพวกเขา ≤ k ต้องการหาจำนวนกลุ่มที่ไม่ซ้อนกัน (disjoint groups)

ตัวอย่าง: points = [[2,2],[3,3],[4,4],[11,11],[12,12]], k = 2 ผลลัพธ์ 2 กลุ่ม: ([2,2],[3,3],[4,4]) และ ([11,11],[12,12])

ขั้นตอนการแก้ปัญหา (Graph + DFS Connected Components)

1. สร้าง adjacency list adj: เชื่อม i-j หากระยะทาง² ≤ k²
2. seen = set(), ans = 0
3. DFS จากทุกโหนดที่ยังไม่ seen:
   • ans += 1, เรียก dfs(i)
4. คืนค่า 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))  # Output: 2

อินพุต

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

เอาต์พุต

2