문제 설명
출발지점 s에서 두 사람이 각각 a, b로 이동할 때, 합승을 포함한 모든 경로 중 최소 택시 요금을 계산하는 문제
예제 입력/출력
n | s | a | b | fares | result |
6 | 4 | 6 | 2 | [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] | 82 |
7 | 3 | 4 | 1 | [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] | 14 |
6 | 4 | 5 | 6 | [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4,8], [4,3,9]] | 18 |
제약 조건
•
•
•
◦
fares 배열의 각 행은 [c, d, f] 형태
◦
◦
문제 풀이
•
출발지점(S)과 도착 지점(A, B)이 정해져 있다.
◦
혼자 택시를 탑승한다 → 출발지점에서 출발하여 다른 지점을 거치지 않고 바로 A, B 지점으로 가는 경우의 비용을 계산한다.
◦
합승한다 → 하나의 지점(K)을 거치고 A, B 지점으로 각각 이동하는 경우의 비용을 계산한다.
•
따라서 출발점 S에서 모든 노드까지의 최단 거리를 계산해야 한다.
◦
이를 위해 플로이드 워셜 혹은 다익스트라 알고리즘을 사용한다.
•
접근1 플로이드-워셜 -
◦
각 노드 k를 중간 경유지로 설정하여, 모든 노드 쌍 (i, j) 간 최단 거리를 갱신한다.
◦
모든 노드 간 최단 거리를 미리 구한 후, S → T, T → A, T → B의 최소 비용을 구한다.
•
접근2 다익스트라 -
◦
이 문제에서는 특정 출발점에서의 최단 거리만 필요하기 때문에 다익스트라 알고리즘을 활용하면 더 효율적으로 해결할 수 있다.
◦
다익스트라 알고리즘을 세 번만 실행하면 된다.
1.
S에서 모든 노드까지의 최단 거리 → dist_from_s
2.
A에서 모든 노드까지의 최단 거리 → dist_from_a
3.
B에서 모든 노드까지의 최단 거리 → dist_from_b
풀이 코드
•
접근1 플로이드-워셜 -
import heapq
INF = int(1e9)
def solution(n, s, a, b, fares):
dists = [[INF] * (n + 1) for _ in range(n + 1)]
# 거리 행렬 초기화
for i in range(1, n + 1):
for j in range(1, n + 1):
if i == j:
dists[i][j] = 0
for c, d, f in fares:
dists[c][d] = f
dists[d][c] = f
# 플루이드워셜 알고리즘
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])
ans = INF
for t in range(1, n + 1):
ans = min(ans, dists[s][t] + dists[t][a] + dists[t][b])
return ans
Python
복사
•
접근2 다익스트라 -
import heapq
INF = int(1e9)
def dijkstra(start):
global n, adj_list
hq = []
heapq.heappush(hq, (0, start)) # (요금, 노드)
dists = [INF] * (n + 1)
dists[start] = 0
while hq:
cur_cost, cur_node = heapq.heappop(hq)
for adj_node, adj_cost in adj_list[cur_node]:
tmp_dist = dists[cur_node] + adj_cost
if tmp_dist < dists[adj_node]:
dists[adj_node] = tmp_dist
heapq.heappush(hq, (adj_cost, adj_node))
return dists
def solution(_n, s, a, b, fares):
global n, adj_list
n = _n
adj_list = [[] for _ in range(n + 1)] # (노드, 요금)
for c, d, f in fares:
adj_list[c].append((d, f))
adj_list[d].append((c, f))
dist_from_s = dijkstra(s)
dist_from_a = dijkstra(a)
dist_from_b = dijkstra(b)
ans = INF
for i in range(1, n + 1):
ans = min(ans, dist_from_s[i] + dist_from_a[i] + dist_from_b[i])
return ans
Python
복사
