ปัญหา: กำหนด 2D Matrix หาว่ามี Cycle ของค่าเดียวกันหรือไม่ โดยเคลื่อนที่ได้ 4 ทิศทาง (บน ล่าง ซ้าย ขวา) ไม่สามารถกลับไป Cell ที่เพิ่งมาจากได้ทันที (No Immediate Backtrack)
อัลกอริทึม: DFS + Cycle Detection
- สร้าง Visited Matrix (R×C) เริ่มต้น False
- สำหรับแต่ละ Cell ที่ยังไม่ Visited:
- รัน DFS จาก Cell นั้น
- DFS ใช้ Stack: เก็บ `(current_cell, parent_cell)`
- ถ้าเจอ Neighbor ที่ Visited แล้ว และไม่ใช่ Parent → พบ Cycle
การติดตั้ง
class Solution:
def solve(self, matrix):
R = len(matrix)
C = len(matrix[0])
def get_neighbors(i, j):
val = matrix[i][j]
for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
ni, nj = i + di, j + dj
if 0 <= ni < R and 0 <= nj < C and matrix[ni][nj] == val:
yield ni, nj
vis = [[False] * C for _ in range(R)]
def dfs(root):
stack = [(root, None)] # (current, parent)
vis[root[0]][root[1]] = True
while stack:
v, prev = stack.pop()
for w in get_neighbors(*v):
if w != prev: # ไม่ใช่ Parent (ป้องกัน Backtrack ทันที)
if not vis[w[0]][w[1]]:
vis[w[0]][w[1]] = True
stack.append((w, v))
else:
# เจอ Visited Node ที่ไม่ใช่ Parent = Cycle
return True
return False
for i in range(R):
for j in range(C):
if not vis[i][j]:
if dfs((i, j)):
return True
return False
# Test
ob = Solution()
matrix = [
[2, 2, 2, 1],
[2, 1, 2, 1],
[2, 2, 2, 1]
]
print(ob.solve(matrix)) # True
คำอธิบาย
get_neighbors: หาเพื่อนบ้าน 4 ทิศทางที่มีค่าเท่ากันvis: ติดตาม Cell ที่เยี่ยมชมแล้ว (Global Visited)dfs(root): Iterative DFS ด้วย Stack เก็บ `(node, parent)`ถ้าเจอ Neighbor ที่ Visited แล้ว และไม่ใช่ Parent → Cycle (Back Edge)
Main Loop: เริ่ม DFS จากทุก Cell ที่ยังไม่ Visited
ผลลัพธ์ตัวอย่าง
Matrix:
2 2 2 1
2 1 2 1
2 2 2 1
Cycle: 2's ที่มุมซ้ายบน → ขวา → ล่าง → ซ้าย → บน (กลับจุดเริ่มต้น)
Output: True
Complexity
- Time: O(R × C) - แต่ละ Cell เข้า Stack สูงสุด 1 ครั้ง
- Space: O(R × C) - Visited Matrix + Stack
ข้อสังเกตสำคัญ
- Global Visited (`vis`) ป้องกันการ DFS ซ้ำ Component เดียว
- Parent Tracking ป้องกัน False Positive จากการกลับทันที (A→B→A)
- ทำงานได้กับ Matrix ขนาดใหญ่ (Iterative DFS ไม่ Recursion Limit)
- Cycle ต้องมีความยาว ≥ 4 (ใน Grid 4-directional)
Variations
# หา Cycle ทั้งหมด (ไม่แค่ True/False)
def find_all_cycles(matrix):
cycles = []
# ... เก็บ Path เมื่อเจอ Cycle ...
return cycles
# 8-Directional (Diagonal)
for di, dj in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]:
...
