문제 개요
항구(port) 네트워크에서 배송 작업의 총비용을 계산하는 문제를 살펴보겠습니다. ports라는 리스트가 주어지며, ports[i]는 i번 항구와 직접 연결된 항구들의 목록을 나타냅니다. 또 다른 리스트인 shipments에는 배송 요청 정보가 담겨 있고, 각 요청은 [i, j] 형태로 표현되어 i번 항구에서 j번 항구로 화물을 보내야 함을 의미합니다.
이때 i번 항구에서 j번 항구로 배송하는 비용은 두 항구 사이의 최단 경로 길이이며, 우리는 모든 배송 요청을 완료하기 위해 필요한 총비용을 구해야 합니다.
예를 들어, 다음과 같은 입력이 주어진다고 가정해 봅시다.
- ports = [[1, 4], [2], [3], [0, 1], []]
- shipments = [[1, 4]]
이 경우 출력값은 4가 됩니다. 왜냐하면 1번 항구에서 4번 항구까지의 최단 경로는 1 → 2 → 3 → 0 → 4이고, 이 경로의 길이가 곧 배송 비용이기 때문입니다.
풀이 접근 방법
이 문제는 그래프의 모든 노드 쌍 사이의 최단 거리를 구해야 하므로, 플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하는 것이 가장 효율적입니다. 해결 단계는 다음과 같습니다.
- n := ports의 크기(총 항구 수)로 설정합니다.
- dist := ports 목록을 기반으로 인접 행렬을 생성합니다. 자기 자신까지의 거리는 0, 직접 연결된 항구 간 거리는 1, 나머지는 무한대(INF)로 초기화합니다.
- 플로이드-워셜 알고리즘을 적용해 모든 항구 쌍 간의 최단 거리를 계산합니다.
즉, dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k])를 반복적으로 갱신합니다. - 모든 배송 요청 [i, j]에 대해 dist[i][j]가 무한대가 아닌 경우에만 해당 거리 값을 결과 리스트에 추가합니다.
- 생성된 리스트 값들의 합계를 반환합니다.
구현 예제
아래는 위 알고리즘을 파이썬으로 구현한 코드입니다.
class Solution:
def solve(self, ports, shipments):
n = len(ports)
INF = 10 ** 10
dist = [[INF for _ in range(n)] for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for i in range(n):
for j in ports[i]:
dist[i][j] = 1
for j in range(n):
for i in range(n):
for k in range(n):
dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k])
return sum(dist[i][j] for i, j in shipments if dist[i][j] != INF)
ob = Solution()
ports = [[1, 4],[2],[3],[0, 1],[]]
shipments = [[1, 4]]
print(ob.solve(ports, shipments))
입력
[[1, 4],[2],[3],[0, 1],[]], [[1, 4]]
출력
4
복잡도 분석
플로이드-워셜 알고리즘은 세 번의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)입니다. 여기서 n은 항구의 개수입니다. 공간 복잡도는 인접 행렬을 저장하기 위해 O(n²)이 필요합니다. 항구 수가 많지 않은 상황에서는 매우 실용적인 접근 방식이며, 배송 요청이 여러 개일 때도 미리 계산해 둔 최단 거리 행렬을 재사용할 수 있다는 장점이 있습니다.