'Manhattan distance' 태그의 글 목록

0과 1로 이뤄진 2차원 배열이 주어지고 1은 home을 의미한다. 모든 home으로의 거리 합이 최소인 지점(point)를 찾는 문제다. 거리는 Manhattan Distance를 활용한다. 제약 사항(constraint)에 의하면 2차원 배열의 최대 크기는 200(m) x 200(n)으로 크지 않기에 O (m x n)으로 풀이가 가능하지만, 더 효율적인 방법이 있을 것으로 생각된다. class Solution: def minTotalDistance(self, grid: List[List[int]]) -> int: m, n = len(grid[0]), len(grid) hL = [] for i in range(n): for j in range(m): if grid[i][j] == 1: hL.append..