[LeetCode] 296. Best Meeting Point

 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([i, j])
                    
        x = y = math.inf
        for i in range(n):
            d = 0
            for j in range(len(hL)):
                d += abs(i - hL[j][0])
            if x > d:
                x = d
        for i in range(m):
            d = 0
            for j in range(len(hL)):
                d += abs(i - hL[j][1])
            if y > d:
                y = d

        return x + y

 

* Manhattan Distance

: 대각선 거리가 아닌 가로, 세로 방식으로 움직일 때의 거리의 합으로 생각하면 된다.

 

 

 

참고

- https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC