[LeetCode]Find All Groups of Farmland

https://leetcode.com/problems/find-all-groups-of-farmland/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

이어진 농토들에서 각각 가장 왼쪽, 가장 오른쪽 지점의 좌표를 구하는 문제입니다. 정답에서 농토의 순서는 상관없습니다.

 

처음 시도한 답안

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        m = len(land)
        n = len(land[0])
        answer = []

        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or land[i][j] == 0:
                return [0,0]

            land[i][j] = 0

            # 상하좌우가 아닌 하, 우 로만 탐색            
            max_i1, max_j1 = dfs(i+1, j)
            max_i2, max_j2 = dfs(i, j+1)

            # 오른쪽 아래 부분은 i,j 좌표 값이 가장 큰 지점임. 따라서 max 활용
            max_i = max(i, max_i1, max_i2)
            max_j = max(j, max_j1, max_j2)

            return [max_i, max_j]


        for i in range(m):
            for j in range(n):
                if land[i][j] == 1:
                    # 이중 순회를 통해 작은 지점부터 방문하니까 i,j가 왼쪽 위 부분임
                    # DFS를 통해 가장 큰 지점(오른쪽 아래 부분)을 구함
                    max_i, max_j = dfs(i, j)
                    answer.append([i, j, max_i, max_j])

        return answer

접근 방법

1. land를 이중 순회하면서 dfs로 탐색합니다.
2. dfs를 수행하면 가장 왼쪽위 지점과 가장 오른쪽아래 지점을 리턴받습니다.
3. dfs 내부에서
   1. 방문할 수 없는 지점이거나 이미 방문한 곳은 탐색을 중지합니다.
   2. 방문처리를 수행합니다.
   3. 왼쪽 위 지점의 좌표는 이중 순회에서 결정됩니다. 따라서 오른쪽과 아래로만 탐색합니다.
   4. 탐색한 결과중에서 가장 큰 좌표를 갖는 i, j 를 저장합니다.
   5. 가장 큰 값인 i, j (가장 오른쪽 아래)를 리턴합니다.
4. 이중 순회에서 선택한 i,j 그리고 가장 큰 i,j를 정답에 추가합니다.

해당 문제에서 왼쪽위와 오른쪽 아래의 경계는 가장 작은 i,j 와 가장 큰 i,j 지점을 찾는 것과 동일합니다.

가장 작은 i,j의 경우에는 이중 순회하면서 순차적으로 구하면서 자동으로 구해지고, 가장 큰 i,j의 경우에는 DFS 탐색에서 가장 큰 i,j값을 찾는 것으로 구할 수 있습니다.

 

경계를 갖는 지점의 i,j가 가장 작고 크다는 것을 알기에 어려웠던 문제 였습니다.