LeetCode No.1992 (T)

LeetCode No.1992 Find All Groups of Farmland

주어진 2차원 배열에서, 0은 숲을 나타내고 1은 농지를 나타낸다.
땅을 관리하기 위해, 직사각형 범위 내에서 이어져있는 땅을 group이라고 부르기로 했다.
하나의 그룹 안에 들어있는 땅은, 다른 그룹 안에 들어 있지 않다.
이 때, 각 그룹의 왼쪽 위 꼭지점과 오른쪽 아래 꼭지점을 포함하고 있는 농지의 좌표를 담아서 반환하라.

---

제한 사항

농지 land에 대해 m == len(land), n == len(land[i])이다.
1 <= m, n <= 300
land안의 값은 0과 1만으로 이루어져 있다.
개개의 group은 직사각형 모양으로 되어 있다.

---

처음 내 생각

• 그래프 탐색 유형 DFS, BFS에 대해 공부하려고 고른 연습 문제.
• 최근 그래프 탐색 문제에서 아주 골때리는 상황을 많이 겪었다.
• 릿코드에서 작년 한 해 동안 연습해 왔고, DFS BFS도 당연히 풀어봤다. 하지만 파이썬으로 넘어오면서 문제가 생기기 시작했다.
• 스위프트에서는 탐색을 위한 별도의 함수를 정의할 때, inout을 명시해줘야 했다. 그래야 함수 밖의 값을 바꿀 수 있었다.
• 하지만 익히 알던 대로 파이썬은 그게 별도의 표시 없어도 된다고 했다. 근데 어떻게?
• 농담이 아니라, 이걸 어떻게 리턴해야 적용할 수 있을까? 고민했었다...
• 문제의 포인트는 금방 파악했다. 하나의 '그룹' 안에 있는 모든 좌표를 돌아다녀본 다음에, 모두가 끝에 다다르면 비로소 하나의 덩어리로 묶고 그 왼쪽 위 셀과 오른쪽 아래 셀을 찾으면 되는 거니까.

---

혼란스럽지만 기억을 되살려 보자

• 함수 안에서 함수를 재정의하면서, inout 키워드만 없는 스위프트 함수처럼 짜 봤다.
  • 원래대로라면 더 탐구하고 써 봤어야겠지만, 알고리즘 때문에 파이썬을 들입다 팔 시간은 없다..
• 풀이 자체는, 해당 그룹에 들어가 있는 모든 땅을 배열에 담은 다음에, 그 배열을 정렬하고, 왼쪽 위 칸과 오른쪽 아래 칸을 뽑아서 넣으면 된다는 것이다.
• 방문한 배열을 표시하는 것도 잊으면 안 되고.

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        result = []
        
        def traverse(row, col, grid, points):
            if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] == 0:
                return
            
            points.append([row, col])
            grid[row][col] = 0
            
            dy = [-1, 1, 0, 0]
            dx = [0, 0, -1, 1]
            
            for i in range(4):
                ny = row + dy[i]
                nx = col + dx[i]
                traverse(ny, nx, grid, points)
            
        for i in range(len(land)):
            for j in range(len(land[i])):
                points = []
                traverse(i, j, land, points)
                points.sort(key = lambda x: (x[0], x[1]))
                if points:
                    territory = points[0] + points[-1]
                    result.append(territory)
        
        return result

• 놀랍게도, 시간 효율이 꽤나 박살나긴 했지만, 어쨌든 맞았다!

---

용기? 깨달음?

• 앞으로도 이렇게 짜면 되겠구나! 하고 자신감을 얻은 것은 당연지사.
• 다만 알고리즘 문제라는 것들은 항상 창의적으로 엿을 먹이기 때문에, inout의 그림을 상상했을 땐 오늘처럼 짜면 된다는 것 정도 알아두자.
• 다음번엔 아예 메서드를 따로 분리해서 작성해 보는 것도 좋겠다.