[LeetCode] 1992. Find All Groups of Farmland

- Problem

1992. Find All Groups of Farmland

- 내 풀이

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        def bfs(y, x):
            q = collections.deque([[y, x]])
            land[y][x] = -1

            while q:
                y, x = q.popleft()
                for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    ny = y + dy
                    nx = x + dx

                    if 0 <= ny < M and 0 <= nx < N and land[ny][nx] == 1:
                        land[ny][nx] = -1
                        q.append([ny, nx])
            
            return [y, x]
        
        M, N = len(land), len(land[0])
        answer = []
        for i in range(M):
            for j in range(N):
                if land[i][j] == 1:
                    top_left_coordinate = [i, j]
                    bottom_right_coordinate = bfs(i, j)
                    answer.append(top_left_coordinate + bottom_right_coordinate)

        return answer

• 시간 복잡도: O(MN)
• 공간 복잡도: O(1)

- 결과