문제 요약
두 사람이 같은 출발 지점 s에서 택시를 타고 각자의 도착 지점 a, b로 이동한다.
두 사람은 경로 일부를 합승할 수 있고, 중간 지점에서 각자 택시를 따로 탈 수 있다.
두 사람이 모두 귀가하기 위한 최소 택시 요금을 구해야 한다.
간선은 양방향이며, 같은 경로를 반대 방향으로 이동해도 요금은 같다.
핵심 아이디어
합승을 끝내는 지점을 k라고 생각한다.
두 사람은 출발 지점 s에서 k까지 함께 이동하고, k에서 각자의 도착 지점으로 따로 이동한다.
전체 비용은 다음 세 최단 거리의 합이다.
출발점 s -> 합승 종료 지점 k
+ 합승 종료 지점 k -> A의 도착점 a
+ 합승 종료 지점 k -> B의 도착점 b식으로 표현하면 다음과 같다.
distance[s][k] + distance[k][a] + distance[k][b]합승을 전혀 하지 않는 경우도 k가 s인 경우에 포함된다.
따라서 모든 지점을 합승 종료 지점으로 가정하고 비용의 최솟값을 구하면 된다.
이를 위해 모든 지점 쌍의 최단 거리를 구하는 플로이드-워셜 알고리즘을 사용한다.
플로이드-워셜 알고리즘
플로이드-워셜은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다.
distance[i][j]를 i번 지점에서 j번 지점까지의 최단 거리라고 정의한다.
중간 지점 k를 거쳐 가는 경로가 더 짧은지 확인한다.
distance[i][j] = min(
distance[i][j],
distance[i][k] + distance[k][j]
)모든 중간 지점 k를 차례대로 허용하면, 반복이 끝난 뒤 distance 배열에는 모든 지점 쌍의 최단 거리가 저장된다.
거리 배열 초기화
지점 번호는 1부터 n까지 사용하므로 크기가 n + 1인 2차원 배열을 사용한다.
INF = float("inf")
distance = [
[INF] * (n + 1)
for _ in range(n + 1)
]자기 자신으로 이동하는 비용은 0이다.
for point in range(1, n + 1):
distance[point][point] = 0입력으로 주어진 택시 요금은 양방향으로 저장한다.
for start, end, fare in fares:
distance[start][end] = fare
distance[end][start] = fare모든 지점 쌍의 최단 거리 계산
중간 지점을 가장 바깥 반복문으로 둔다.
for middle in range(1, n + 1):
for start in range(1, n + 1):
for end in range(1, n + 1):
distance[start][end] = min(
distance[start][end],
distance[start][middle]
+ distance[middle][end]
)이 순서가 중요한 이유는 middle보다 작은 번호의 중간 지점만 사용한 최단 경로를 먼저 완성한 뒤, middle을 추가로 사용할 수 있게 해야 하기 때문이다.
합승 종료 지점 선택
모든 지점을 합승 종료 지점으로 확인한다.
answer = INF
for split in range(1, n + 1):
total_fare = (
distance[s][split]
+ distance[split][a]
+ distance[split][b]
)
answer = min(answer, total_fare)split이 출발 지점 s라면 합승 구간이 없는 경우다.
split이 a 또는 b라면 한 사람의 집까지 합승한 뒤 다른 한 사람만 따로 이동하는 경우다.
따라서 가능한 모든 합승 방식이 포함된다.
풀이 과정
- 모든 지점 쌍의 거리를 무한대로 초기화한다.
- 자기 자신까지의 거리를 0으로 설정한다.
- 각 택시 경로를 양방향 거리 배열에 저장한다.
- 플로이드-워셜로 모든 지점 쌍의 최단 거리를 구한다.
- 모든 지점을 합승 종료 지점으로 가정한다.
- 세 최단 거리의 합 중 최솟값을 반환한다.
Python 코드
def solution(n, s, a, b, fares):
INF = float("inf")
distance = [
[INF] * (n + 1)
for _ in range(n + 1)
]
# 자기 자신으로 이동하는 비용은 0이다.
for point in range(1, n + 1):
distance[point][point] = 0
# 택시 경로는 양방향이다.
for start, end, fare in fares:
distance[start][end] = fare
distance[end][start] = fare
# 모든 지점 쌍의 최단 거리를 계산한다.
for middle in range(1, n + 1):
for start in range(1, n + 1):
for end in range(1, n + 1):
distance[start][end] = min(
distance[start][end],
distance[start][middle]
+ distance[middle][end]
)
answer = INF
# 모든 지점을 합승 종료 지점으로 확인한다.
for split in range(1, n + 1):
total_fare = (
distance[s][split]
+ distance[split][a]
+ distance[split][b]
)
answer = min(answer, total_fare)
return answer코드 설명
distance 배열
distance[start][end]start번 지점에서 end번 지점까지의 현재 최단 요금이다.
처음에는 직접 연결된 경로의 요금만 알고 있으므로, 연결 정보가 없는 경로는 무한대로 둔다.
양방향 경로
distance[start][end] = fare
distance[end][start] = fare문제에서 택시 요금은 이동 방향에 따라 달라지지 않는다.
따라서 한 경로의 요금을 양쪽 방향에 모두 저장해야 한다.
middle
for middle in range(1, n + 1):현재 middle 지점을 경유하는 경로를 새로 허용한다.
start에서 end로 직접 가는 것보다 middle을 거쳐 가는 비용이 더 작으면 최단 거리를 갱신한다.
split
for split in range(1, n + 1):두 사람이 같이 택시에서 내리고 각자 이동을 시작하는 지점이다.
한 지점만 합승 종료 지점으로 선택하면 모든 가능한 합승 경로를 비교할 수 있다.
예시
문제의 예시처럼 출발점이 4, A의 도착점이 6, B의 도착점이 2라고 하자.
5번 지점에서 합승을 끝내는 경우 비용은 다음과 같다.
4 -> 5 합승 비용: 34
5 -> 6 A 단독 비용: 2
5 -> 2 B 단독 비용: 46
전체 비용: 34 + 2 + 46 = 82모든 지점을 split으로 확인했을 때 82가 최솟값이라면 정답은 82다.
시간 복잡도
지점의 개수를 N이라고 하자.
플로이드-워셜은 세 겹의 반복문을 사용한다.
O(N^3)N은 최대 200이므로 약 800만 번의 거리 갱신으로 처리할 수 있다.
합승 종료 지점을 확인하는 과정은 O(N)이다.
전체 시간 복잡도는 플로이드-워셜이 지배한다.
O(N^3)공간 복잡도
모든 지점 쌍의 최단 거리를 저장하는 2차원 배열을 사용한다.
O(N^2)정리
이 문제는 합승 종료 지점을 하나 정하면 비용을 세 개의 최단 거리로 분리할 수 있는 최단 경로 문제다.
모든 지점 쌍의 최단 거리 계산
각 지점을 합승 종료 지점으로 가정
s -> split + split -> a + split -> b 계산
가장 작은 비용 반환합승 구간을 직접 구성할 필요 없이, 모든 지점을 분기점으로 가정해 세 최단 거리의 합을 비교하는 것이 핵심이다.
