모든 주문을 보내는 최소 배송 비용

자바스크립트 코딩테스트 문제로 min-cost-flow 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard min-cost-flow 함수명: minimumCostCourierFlow 제한 시간: 500ms

여러 공급 허브에서 여러 주문 허브로 물량을 보내야 할 때, 모든 주문을 채우는 최소 배송 비용을 구하는 문제입니다.

문제 설명

허브는 0번부터 n - 1번까지 있습니다.

supplies는 [hub, amount] 형태이며, 해당 허브에서 보낼 수 있는 물량을 뜻합니다. demands는 [hub, amount] 형태이며, 해당 허브가 받아야 하는 주문 물량을 뜻합니다.

배송 경로 routes의 각 원소는 [from, to, capacity, cost] 형태입니다.

• from 허브에서 to 허브로만 이동할 수 있습니다.
• 이 경로로 최대 capacity만큼 보낼 수 있습니다.
• 물량 1개를 이 경로로 보낼 때마다 cost가 듭니다.

모든 주문 물량을 정확히 채우는 데 필요한 최소 총 비용을 반환하는 minimumCostCourierFlow 함수를 작성하세요. 모든 주문을 채울 수 없다면 -1을 반환합니다.

제한사항

• 1 <= n <= 80
• 0 <= supplies.length, demands.length <= n
• 0 <= routes.length <= 500
• supplies[i] = [hub, amount]
• demands[i] = [hub, amount]
• routes[i] = [from, to, capacity, cost]
• 0 <= hub, from, to < n
• from !== to
• 1 <= amount <= 1000
• 1 <= capacity <= 1000
• 0 <= cost <= 100000
• 같은 두 허브 사이에 여러 경로가 있을 수 있습니다.
• 공급 허브와 주문 허브가 겹칠 수 있으며, 같은 허브 안에서 바로 충당되는 물량은 비용 없이 처리할 수 있습니다.
• 모든 주문량을 보낼 수 없거나 총 공급량이 총 주문량보다 작으면 -1을 반환합니다.
• 반환값은 JavaScript의 Number로 안전하게 표현되는 범위 안에 들어옵니다.

예시

• 입력:
  • n = 4
  • supplies = [[0, 2]]
  • demands = [[3, 2]]
  • routes = [[0, 1, 2, 1], [1, 3, 2, 2], [0, 2, 2, 3], [2, 3, 2, 1]] → 출력: 6
• 입력:
  • n = 5
  • supplies = [[0, 3], [1, 1]]
  • demands = [[3, 2], [4, 2]]
  • routes = [[0, 2, 2, 2], [1, 2, 2, 1], [2, 3, 3, 2], [2, 4, 2, 3], [0, 4, 1, 10]] → 출력: 22
• 입력:
  • n = 3
  • supplies = [[0, 2]]
  • demands = [[2, 2]]
  • routes = [[0, 1, 1, 5]] → 출력: -1

힌트

• 한 공급 허브에서 한 주문 허브로만 보내는 문제가 아닙니다. 여러 경로로 나누어 보내는 선택이 필요합니다.
• 공급 허브를 super source에, 주문 허브를 super sink에 연결하면 하나의 유량 네트워크로 볼 수 있습니다.
• 매번 가장 싼 증가 경로를 찾되, 이미 흘린 유량을 되돌릴 수 있는 역방향 간선도 함께 관리해야 합니다.

해설

이 문제는 최단 경로와 유량이 함께 필요한 최소 비용 최대 유량 문제입니다.

먼저 네트워크를 다음처럼 확장합니다.

1. 새 출발점 S를 만들고, 각 공급 허브로 amount 용량과 비용 0인 간선을 연결합니다.
2. 각 주문 허브에서 새 도착점 T로 amount 용량과 비용 0인 간선을 연결합니다.
3. 입력으로 받은 배송 경로를 그대로 용량 capacity, 비용 cost인 방향 간선으로 추가합니다.

이제 S에서 T까지 총 주문량만큼의 유량을 보내는 최소 비용을 찾으면 됩니다.

가장 직접적인 방법은 다음 과정을 반복하는 것입니다.

1. 잔여 용량이 남은 간선만 사용해 S에서 T까지 비용이 가장 작은 경로를 찾습니다.
2. 그 경로에 흘릴 수 있는 최대 물량을 보냅니다.
3. 사용한 간선의 잔여 용량을 줄이고, 되돌릴 수 있도록 역방향 간선의 잔여 용량을 늘립니다.
4. 보낸 물량과 경로 비용을 곱해 총 비용에 더합니다.

비용이 음수가 아닌 입력이어도, 역방향 간선은 음수 비용을 가질 수 있습니다. 그래서 구현에서는 잠재값(potential)을 함께 관리해 다익스트라가 음수 간선 때문에 깨지지 않도록 보정하는 방식이 안정적입니다.

모든 반복이 끝났는데 보낸 총 물량이 전체 주문량보다 작다면, 네트워크 용량이나 연결이 부족한 것이므로 -1을 반환합니다. 그렇지 않으면 누적한 최소 비용이 정답입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

입력값 []

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.