Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 풀어보는 캠퍼스 자전거 배정 문제 (Campus Bikes II)

문제 소개

하나의 2차원 격자(grid)가 캠퍼스를 나타낸다고 가정해 보겠습니다. 이 캠퍼스에는 N명의 워커(worker)와 M대의 자전거(bike)가 있으며, N ≤ M 조건이 성립합니다. 각 워커와 자전거는 격자 위의 2차원 좌표에 위치해 있습니다.

우리의 목표는 각 워커에게 서로 다른 자전거를 하나씩 배정하되, 모든 워커와 배정된 자전거 사이의 맨해튼 거리(Manhattan Distance) 합이 최소가 되도록 하는 것입니다.

두 점 p1과 p2 사이의 맨해튼 거리는 다음과 같이 정의됩니다.

(p1, p2) = |p1.x − p2.x| + |p1.y − p2.y|

예를 들어 workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]이 입력으로 주어진다면, 최적의 배정 결과는 6이 됩니다.

접근 방법: 백트래킹 + 메모이제이션

이 문제는 모든 가능한 배정 조합을 탐색하는 백트래킹(backtracking) 방식으로 해결할 수 있습니다. 다만 단순 완전 탐색은 중복된 상태를 반복적으로 계산하게 되므로, 메모이제이션(memoization)을 활용하여 이미 계산한 결과를 캐싱하면 성능을 크게 향상시킬 수 있습니다.

핵심 아이디어는 다음과 같습니다.

  • 워커를 순서대로 한 명씩 처리하며, 아직 사용되지 않은 자전거를 하나씩 배정해 봅니다.
  • 현재 상태는 (처리 중인 워커 인덱스, 사용 중인 자전거 목록)으로 표현됩니다.
  • 동일한 상태가 다시 등장하면 저장해 둔 최솟값을 즉시 반환하여 중복 연산을 제거합니다.

단계별 풀이 과정

  1. helper() 함수 정의: 두 좌표 a, b를 받아 맨해튼 거리 |a[0]−b[0]| + |a[1]−b[1]|을 반환합니다.
  2. solve() 함수 정의: bikes, workers, bikev(자전거 사용 여부 배열), 그리고 현재 워커 인덱스 i(기본값 0)를 매개변수로 받습니다.
  3. info := (i, bikev) 형태의 상태 정보를 만듭니다.
  4. info가 memo에 이미 존재하면, 해당 값을 그대로 반환합니다.
  5. i가 workers의 길이와 같으면, 모든 워커에게 자전거를 배정했다는 의미이므로 0을 반환합니다.
  6. temp := 무한대(infinity)로 초기화합니다.
  7. j를 0부터 bikes의 크기까지 반복하면서 다음을 수행합니다.
    • bikev[j]가 아직 사용되지 않았다면:
      • bikev[j] := 1로 표시하여 자전거를 사용 처리합니다.
      • temp := min(temp, helper(workers[i], bikes[j]) + solve(bikes, workers, bikev, i+1))로 최솟값을 갱신합니다.
      • bikev[j] := 0으로 되돌려 다른 경우의 수를 탐색할 수 있게 합니다(백트래킹).
  8. memo[info] := temp로 결과를 저장한 뒤 temp를 반환합니다.
  9. assignBikes() 함수 정의: bikes와 같은 크기의 False로 채워진 bikev 리스트와 빈 memo 딕셔너리를 생성하고, solve(bikes, workers, bikev)의 결과를 반환합니다.

파이썬 구현 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

class Solution(object):
    def helper(self, a, b):
        return abs((a[0]-b[0])) + abs((a[1]-b[1]))

    def solve(self, bikes, workers, bikev, i=0):
        info = (i, tuple(bikev))
        if info in self.memo:
            return self.memo[info]
        if i == len(workers):
            return 0
        temp = float('inf')
        for j in range(len(bikes)):
            if not bikev[j]:
                bikev[j] = 1
                temp = min(temp, self.helper(workers[i], bikes[j])
                           + self.solve(bikes, workers, bikev, i+1))
                bikev[j] = 0
        self.memo[info] = temp
        return temp

    def assignBikes(self, workers, bikes):
        bikev = [False for i in range(len(bikes))]
        self.memo = {}
        return self.solve(bikes, workers, bikev)

ob = Solution()
print(ob.assignBikes([[0,0],[2,1]], [[1,2],[3,3]]))

입력

[[0,0],[2,1]] [[1,2],[3,3]]

출력

6

복잡도 분석

메모이제이션을 적용하면 전체 상태의 수는 (워커 수 × 자전거 사용 조합의 수), 즉 최대 N × 2M개입니다. 각 상태에서 최대 M개의 자전거를 시도하므로, 시간 복잡도는 O(N × M × 2M)입니다. 단순 완전 탐색의 O(M! / (M−N)!)에 비해 훨씬 효율적이며, 입력 크기가 작은 이 문제의 제약 조건에서 충분히 빠르게 동작합니다.