[2024] day 112. Leetcode 1992. Find All Groups of Farmland

gunny·2024년 4월 24일

leetcode 1992. Find All Groups of Farmland leetcode 1992. Find All Groups of Farmland python

코딩테스트

목록 보기

425/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 20일 (토)
Leetcode daily problem

1992. Find All Groups of Farmland

https://leetcode.com/problems/find-all-groups-of-farmland/?envType=daily-question&envId=2024-04-20

Problem

m x n 이진 행렬 'land'가 주어질 때, 여기서 0은 1헥타르의 산림지를 나타내고 1은 1헥타르의 농지를 나타낸다.

토지를 체계적으로 유지하기 위해 농지로 구성된 직사각형의 헥타르 면적이 지정되어 있고, 이러한 직사각형 영역을 'groups'이라고 한다. 각 그륩은 인접하지 않은 특성을 가지고 있는데 즉, 한 그룹의 농지가 다른 그룹의 다른 농지와 4방향으로 인접하지 않는 다는 것이다.

land는 land의 좌측상단을 (0, 0), 우측하단을 (m-1, n-1)으로 하는 좌표계로 나타낼 수 있다. 각 land group의 왼쪽 상단과 오른쪽 하단의 좌표를 찾는다. 왼쪽 상단이 (r1, c1)이고 오른쪽 하단이 (r2, c2)인 농지 그룹은 4 길이 배열 [r1, c1, r2, c2]로 표시 된다.

land의 각 농경지 그룹(1)에 대해 위에서 설명한 4개의 길이 배열을 포함하는 2D 배열을 반환한다. 농지 그룹이 없으면 빈 배열을 반환한다. 농경지 그룹은 어떤 순서로든 답변을 반환할 수 있다.

Solution

Graph serach algorithm (DFS, BFS)

해당 문제는 그래프 탐색 알고리즘 중 하나로 해결할 수 있는데,
DFS를 통해서 해당 문제를 해결해본다면 주어진 그리드를 탐색하면서 각 농지 그룹을 식별하고, 해당 그룹의 최소 좌표와 최대 좌표를 추적하여 반환한다.
간단한 가정은 인접한 1들은 같은 그룹에 속한다는 것이므로, 따라서 인접한 1들을 찾아내고 해당 좌표를 방문해 같은 그룹에 속하는지 확인하여 같은 그룹에 있다면 해당 좌표를 추가하여 업데이트 한다.

Code

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        
        ROWS, COLS = len(land), len(land[0])
        ans = []
        
        def dfs(r,c):
            tmp = [r,c]
            row, col = r,c
            
            while row < ROWS and land[row][c]==1:
                row +=1
            
            while col < COLS and land[r][col]==1:
                col +=1
                
            tmp.extend([row-1,col-1])
            
            for i in range(r, row):
                for j in range(c, col):
                    land[i][j] = 0
                    
            return tmp
        
        for r in range(ROWS):
            for c in range(COLS):
                if land[r][c] == 1:
                    ans.append(dfs(r,c))

        return ans