โปรแกรมหาจุดพบปะที่ลดระยะทางรวมน้อยที่สุดใน Grid (Python)

ปัญหา

กำหนด 2D matrix:
0 = ว่าง, 1 = ผนัง, 2 = คน
คนเดินได้ 4 ทิศทาง (บน/ล่าง/ซ้าย/ขวา) ไม่เดินทะลุผนัง
หาจุดพบปะ (ไม่ใช่ผนัง) ที่ minimize ผลรวมระยะทางจากทุกคน

ตัวอย่าง: 3x4 grid → จุดที่ดีที่สุด = มุมล่างขวา, ระยะทางรวม = 7

วิธีแก้: Multi-source BFS จากแต่ละคน

รัน BFS จากแต่ละคน (ค่า 2) คำนวณระยะทางไปทุกเซลล์ แล้วรวมระยะทางทุกคนต่อเซลล์ หาค่าต่ำสุด

อัลกอริทึม

1. หาตำแหน่งคนทั้งหมด (ค่า 2)
2. สำหรับแต่ละคน รัน BFS คำนวณ distance grid
3. รวม distance grids ทุกคน
4. หา min ของผลรวม (เฉพาะเซลล์ที่ไม่ใช่ผนัง)

โค้ด Python

class Solution:
    def solve(self, matrix):
        twos = {}
        costs = {}
        
        # หาตำแหน่งคนและสร้าง cost grids
        for i, row in enumerate(matrix):
            for j, v in enumerate(row):
                if v == 2:
                    twos[(i, j)] = [(i, j, 0)]
                    costs[(i, j)] = [[float('inf')] * len(matrix[0]) for _ in matrix]
        
        # BFS จากแต่ละคน
        for person_pos, queue in twos.items():
            seen = set()
            while queue:
                i, j, cost = queue.pop(0)
                if (i, j) in seen:
                    continue
                seen.add((i, j))
                costs[person_pos][i][j] = cost
                
                for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
                    ni, nj = i + di, j + dj
                    if (0 <= ni < len(matrix) and 0 <= nj < len(matrix[0]) 
                        and matrix[ni][nj] != 1):
                        queue.append((ni, nj, cost + 1))
        
        # หาจุดที่ผลรวมระยะทางน้อยที่สุด
        ans = float('inf')
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                cur_cost = sum(cost_grid[i][j] for cost_grid in costs.values())
                ans = min(ans, cur_cost)
        
        return ans

# ทดสอบ
ob = Solution()
matrix = [
    [2, 0, 1, 0],
    [1, 0, 1, 2],
    [0, 0, 2, 2]
]
print(ob.solve(matrix))  # 7

ความซับซ้อน

• Time: O(P × R × C) - P คน, R×C grid size
• Space: O(P × R × C) - เก็บ cost grid ทุกคน

Optimization: Single BFS with Multiple Sources

หากต้องการ optimize ให้รัน BFS ครั้งเดียวจากทุกคนพร้อมกัน (multi-source BFS) แล้วเก็บจำนวนคนที่ถึงแต่ละเซลล์และระยะทางรวม

from collections import deque

def solve_optimized(self, matrix):
    R, C = len(matrix), len(matrix[0])
    people = [(i, j) for i in range(R) for j in range(C) if matrix[i][j] == 2]
    P = len(people)
    
    total_dist = [[0]*C for _ in range(R)]
    reach_count = [[0]*C for _ in range(R)]
    
    for pi, pj in people:
        seen = [[False]*C for _ in range(R)]
        q = deque([(pi, pj, 0)])
        seen[pi][pj] = True
        
        while q:
            i, j, d = q.popleft()
            total_dist[i][j] += d
            reach_count[i][j] += 1
            
            for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
                ni, nj = i+di, j+dj
                if 0<=ni

Optimized version: O(P × R × C) time แต่ space ลดเหลือ O(R × C)