บทนำ
โจทย์: กำหนด binary matrix (มีแค่ 0 และ 1) หาเส้นทางต่อเนื่องของ 1 ที่ยาวที่สุด โดยอนุญาตให้เปลี่ยน 0 หนึ่งตัวเป็น 1 ได้ ใช้ Depth-First Search (DFS) จัดกลุ่ม 1 ที่ติดกัน แล้วพิจารณา 0 ที่เชื่อมกลุ่มได้มากที่สุด
ตัวอย่าง
Input: [[1, 0], [0, 1]] Output: 3 อธิบาย: เปลี่ยน 0 ที่ (0,1) หรือ (1,0) จะได้เส้นทางยาว 3
โค้ดแก้ปัญหา
def find_neighbors(r, c, n):
"""สร้างเพื่อนบ้าน 4 ทิศทางที่อยู่ใน matrix"""
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if 0 <= nr < n and 0 <= nc < n:
yield nr, nc
def dfs(r, c, index, matrix, n):
"""DFS จัดกลุ่ม 1 ที่ติดกัน ติดป้ายกลับด้วย index คืนขนาดกลุ่ม"""
size = 1
matrix[r][c] = index
for nr, nc in find_neighbors(r, c, n):
if matrix[nr][nc] == 1:
size += dfs(nr, nc, index, matrix, n)
return size
def find_largest_path(matrix):
n = len(matrix)
group_size = {} # index -> ขนาดกลุ่ม
index = 2 # เริ่มที่ 2 เพราะ 0,1 ใช้แล้ว
# 1. จัดกลุ่ม 1 ทั้งหมด
for i in range(n):
for j in range(n):
if matrix[i][j] == 1:
group_size[index] = dfs(i, j, index, matrix, n)
index += 1
# 2. หาขนาดกลุ่มมากที่สุดเดิม
max_path = max(group_size.values()) if group_size else 0
# 3. ลองเปลี่ยนแต่ละ 0 ดูว่าเชื่อมกลุ่มไหนได้
for i in range(n):
for j in range(n):
if matrix[i][j] == 0:
# ดูกลุ่มเพื่อนบ้านที่ติดกัน (index > 1)
neighbor_groups = {matrix[nr][nc] for nr, nc in find_neighbors(i, j, n)
if matrix[nr][nc] > 1}
# ขนาดใหม่ = 1 (ตัว 0 ที่เปลี่ยน) + ผลรวมขนาดกลุ่มเพื่อนบ้านที่ไม่ซ้ำ
combined = 1 + sum(group_size[g] for g in neighbor_groups)
max_path = max(max_path, combined)
return max_path
# ทดสอบ
matrix = [[1, 0], [0, 1]]
print("ความยาวเส้นทางสูงสุด:", find_largest_path(matrix))
ผลลัพธ์
ความยาวเส้นทางสูงสุด: 3
คำอธิบายอัลกอริทึม
- Grouping: DFS หา connected components ของ 1 ทั้งหมด ติดป้ายแต่ละกลุ่มด้วย index (2, 3, 4...) บันทึกขนาดแต่ละกลุ่ม
- Evaluate 0s: สำหรับแต่ละ 0 ดูกลุ่มเพื่อนบ้านที่ติดกัน (unique groups) คำนวณขนาดรวมถ้าเปลี่ยน 0 นี้เป็น 1
- Result: ค่าสูงสุดระหว่างกลุ่มเดิมที่ใหญ่ที่สุด และการรวมกลุ่มผ่าน 0 ตัวใดตัวหนึ่ง
ความซับซ้อน
- เวลา: O(N²) - ทุกเซลล์ถูกเยี่ยมชมคงที่ครั้ง
- พื้นที่: O(N²) - สำหรับ matrix และ recursion stack
