[LeetCode] 1066. Campus Bikes II

1066. Campus Bikes II

Medium

On a campus represented as a 2D grid, there are n workers and m bikes, with n <= m. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

 

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation: 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Example 3:

Input: workers = [[0,0],[1,0],[2,0],[3,0],[4,0]], bikes = [[0,999],[1,999],[2,999],[3,999],[4,999]]
Output: 4995

 

Constraints:

• n == workers.length
• m == bikes.length
• 1 <= n <= m <= 10
• workers[i].length == 2
• bikes[i].length == 2
• 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
• All the workers and the bikes locations are unique.

---

문제 풀이

• 일하는 사람들의 2차원 좌표 배열과 자전거들의 2차원 좌표 배열이 주어진다. 
• 각각의 사람들이 각각의 자전거를 차지한다고 했을때, 사람의 좌표부터 자전거의 거리까지의 총합의 최소값을 구해야한다.
• 거리는 맨하탄 거리로 자전거와 사람의 거리를 계산한다. 
• 제한 사항을 보면 사람들과 자전거들의 최대길이가 10이다. 
• 완전 탐색으로 가능할 것 같지만, 만일 모든 사람들이 모든 자전거를 한번씩 탐색한다면 N^N 시간복잡도가 나올 것이다. 
• 그래서 DFS를 사용하여 완전탐색을 하되, 몇번째 사람인지와 여태 방문한 사람들 번호로 메모이제이션을 활용해야한다.
• 사람들 번호로 탐색을 할때 방문한 자전거들의 번호를 계속해서 저장해준다. 
• memo 배열에 자전거들과 사람들의 거리의 총값을 저장할때는 모든 재귀 호출이 끝나고 적어준다.
• 리턴 조건에서 사람의 번호가 일하는 사람들의 길이를 넘었을때 종료해주도록 설계했기 때문이다.
• 즉, dfs 함수를 호출할때마다 사람의 번호가 1씩 추가가되고 마지막 사람까지의 자전거들의 거리를 계산하고 난 뒤에 그 값을 memo에 저장한다. 
• 저장할때는 사람의 번호와 현재 확인한 자전거들의 번호를 튜플로 넣어 중복을 피한다. 
• for 문으로 모든 자전거를 탐색하기 때문에 이러한 작업이 필요하다. 
• 그리고 확인한 자전거의 visited 체크는 풀어줘야한다. 
• 만일 풀지 않으면 모든 자전거들을 확인할 수 없기 때문이다. 

소스 코드

class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        w_n = len(workers)
        b_n = len(bikes)
        def dis(w, b):
            return abs(b[0] - w[0]) + abs(b[1] - w[1])

        def dfs(w, visited, memo):
            if w >= w_n:
                return 0
            if (w, tuple(visited)) in memo:
                return memo[(w, tuple(visited))]
            
            ans = float('inf')
            for i in range(b_n):
                if i in visited: continue
                visited.add(i)
                ret = dfs(w + 1, visited, memo)
                visited.remove(i)
                ret += dis(workers[w], bikes[i])
                ans = min(ans, ret)
            memo[(w, tuple(visited))] = ans
            return ans
        return dfs(0, set(), dict())