[LeetCode] 1992. Find All Groups of Farmland (Daily Question)

문제

---

You are given a 0-indexed m x n binary matrix land where a 0 represents a hectare of forested land and a 1 represents a hectare of farmland.

To keep the land organized, there are designated rectangular areas of hectares that consist entirely of farmland. These rectangular areas are called groups. No two groups are adjacent, meaning farmland in one group is not four-directionally adjacent to another farmland in a different group.

land can be represented by a coordinate system where the top left corner of land is (0, 0) and the bottom right corner of land is (m-1, n-1). Find the coordinates of the top left and bottom right corner of each group of farmland. A group of farmland with a top left corner at (r1, c1) and a bottom right corner at (r2, c2) is represented by the 4-length array [r1, c1, r2, c2].

Return a 2D array containing the 4-length arrays described above for each group of farmland in land. If there are no groups of farmland, return an empty array. You may return the answer in any order.

 

농토들의 좌상단 좌표와 우하단 좌표들을 찾는 문제이다.

 

Example 1:
Input: land = [[1,0,0],[0,1,1],[0,1,1]]
Output: [[0,0,0,0],[1,1,2,2]]
Explanation: The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0]. The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].

Example 2:
Input: land = [[1,1],[1,1]]
Output: [[0,0,1,1]]
Explanation: The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].

Example 3:
Input: land = [[0]]
Output: []
Explanation: There are no groups of farmland.

 

풀이

---

아이디어

좌상단(0, 0)부터 우하단까지 2중 for문으로 탐색하며 농토 발견 시 BFS로 탐색하고, 해당 섬을 없애버린다.

농토는 사각형이므로 x좌표를 먼저 찾고 y좌표를 찾으면 된다. 

코드

class Solution:

    # 우하단 좌표를 찾는 함수
    def getCorner(self, x_ori, x, y):
        # 농토를 지도에서 제거
        for i in range(x_ori, x+1):
            self.land[i][y] = 0

        # 우측먼저 탐색
        if x+1 < len(self.land) and self.land[x+1][y]:
            return self.getCorner(x_ori, x+1, y)
        # 하단 탐색
        elif y+1 < len(self.land[0]) and self.land[x][y+1]:
            return self.getCorner(x_ori, x, y+1)
        
        return (x, y)

    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        self.land = land
        answer = []
        for i in range(len(land)):
            for j in range(len(land[0])):
                if self.land[i][j]: answer.append([i, j, *self.getCorner(i, i, j)])

        return answer

---

 

후기

---

난이도

모든 땅을 탐색할 필요가 없다는 것만 생각해내면 쉽게 풀 수 있다.

물론 모두 탐색해도 풀 순 있지만, 시간적인 손해가 있을 것이다.