주어진 2차원 배열에서, 0은 숲을 나타내고 1은 농지를 나타낸다.
땅을 관리하기 위해, 직사각형 범위 내에서 이어져있는 땅을 group이라고 부르기로 했다.
하나의 그룹 안에 들어있는 땅은, 다른 그룹 안에 들어 있지 않다.
이 때, 각 그룹의 왼쪽 위 꼭지점과 오른쪽 아래 꼭지점을 포함하고 있는 농지의 좌표를 담아서 반환하라.
농지 land
에 대해 m == len(land)
, n == len(land[i])
이다.
1 <= m, n <= 300
land
안의 값은 0과 1만으로 이루어져 있다.
개개의 group은 직사각형 모양으로 되어 있다.
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
의 그림을 상상했을 땐 오늘처럼 짜면 된다는 것 정도 알아두자.