โปรแกรมนับจำนวนเกาะจากการเพิ่มบล็อกที่ดินทีละอันใน Python

คำอธิบายโจทย์

สมมติว่ามีกริดน้ำขนาดอันตราย เราสามารถเพิ่มบล็อกที่ดินเข้าไปทีละอัน ได้รับรายการพิกัดชื่อ land_requests โดยแต่ละพิกัดเป็น [r, c] (r = แถว, c = คอลัมน์) ต้องหา list ที่แต่ละสมาชิกแสดงจำนวนเกาะที่มีอยู่หลังจากเพิ่มบล็อกที่ดินแต่ละอันจาก land_requests

ตัวอย่าง

อินพุต: land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]

เอาต์พุต: [1, 2, 2, 2, 1]

วิธีแก้ปัญหา

ใช้ Union-Find (Disjoint Set Union) เพื่อจัดการการรวมเกาะแบบไดนามิก:

1. สร้างโครงสร้างข้อมูล Union-Find พร้อม path compression และ union by size
2. สำหรับแต่ละ request: เพิ่มที่ดินใหม่เป็นเกาะแยกต่างหาก (comp + 1)
3. ตรวจสอบเพื่อนบ้าน 4 ทิศทาง ถ้ามีที่ดินอยู่แล้ว ให้ union รวมกัน (comp - 1)
4. บันทึกจำนวนเกาะปัจจุบันลง ans

โค้ด Python

from collections import defaultdict

class Solution:
    def __init__(self):
        self.d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    def search(self, u):
        if u == self.p[u]:
            return u
        self.p[u] = self.search(self.p[u])
        return self.p[u]
    
    def connect(self, u, v):
        pu, pv = self.search(u), self.search(v)
        if pu == pv:
            return
        self.comp -= 1
        if self.size[pu] >= self.size[pv]:
            self.p[pv] = pu
            self.size[pu] += self.size[pv]
        else:
            self.p[pu] = pv
            self.size[pv] += self.size[pu]
    
    def solve(self, land_requests):
        self.idx = 0
        self.mp = {}
        self.p = []
        self.size = []
        self.comp = 0
        ans = []
        
        for request in land_requests:
            i, j = request
            self.mp[(i, j)] = self.idx
            self.p.append(self.idx)
            self.size.append(1)
            self.idx += 1
            self.comp += 1
            
            for k in self.d:
                ni = i + k[1]
                nj = j + k[0]
                if (ni, nj) in self.mp:
                    self.connect(self.mp[(i, j)], self.mp[(ni, nj)])
            
            ans.append(self.comp)
        
        return ans

ob = Solution()
land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]
print(ob.solve(land_requests))

อินพุต

[[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]

เอาต์พุต

[1, 2, 2, 2, 1]