1. 문제 설명
지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요. 만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.
[제한사항]
- 지점갯수 n은 3 이상 200 이하인 자연수입니다.
- 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
- 즉, 출발지점, A의 도착지점, B의 도착지점은 서로 겹치지 않습니다.
- fares는 2차원 정수 배열입니다.
- fares 배열의 크기는 2 이상 n x (n-1) / 2 이하입니다.
- 예를들어, n = 6이라면 fares 배열의 크기는 2 이상 15 이하입니다. (6 x 5 / 2 = 15)
- fares 배열의 각 행은 [c, d, f] 형태입니다.
- c지점과 d지점 사이의 예상 택시요금이 f원이라는 뜻입니다.
- 지점 c, d는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
- 요금 f는 1 이상 100,000 이하인 자연수입니다.
- fares 배열에 두 지점 간 예상 택시요금은 1개만 주어집니다. 즉, [c, d, f]가 있다면 [d, c, f]는 주어지지 않습니다.
- 출발지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.
2. 풀이 전 계획과 생각
- n → 지점의 개수
- s → 출발지점
- a → A의 도착지점
- b → B의 도착지점
- fares : 지점 사이의 예상 택시요금
A, B 두사람이 s에서 출발해서 각자의 도착지점까지 택시를 타고 간다고 가정할 때,
최저 예상 택시요금을 계산하자.
가중치가 있는 최단거리(= 최저 택시요금)는 다익스트라 알고리즘을 이용하면 구하면된다.
N이 200이기에 200log(200 * 199/2)이기에 충분하다.
A가 s에서 출발해서 도착했을 때의 최단거리와 사이의 정점들을 구해주고
B가 s에서 출발해서 도착했을 때의 최단거리와 사이의 정점들을 구해준다.
A와 B의 겹치는 구간을 구해주어 해당 거리를 최저 요금에서 빼준다.
3. 풀이하면서 막혔던 점과 고민
🤔 두명의 시간은 고려해주지 않아도 될까?
시간은 고려사항에 없으므로 괜찮다. (기다리지 않는다, 기다린다 대해 문제 설명에 존재하지 않는다.)
🤔 A와 B의 겹치는 구간이 최저 요금이 나오는 거리라고 단정지을 수 없다. 어떻게 해결해주면 좋을까?
⇒ 합승지점 변수를 두고 합승지점을 모든 vertex마다 바꿔주면서 최단거리를 구해줄 수가 있다.
🤔 합승하지 않으면 어떻게 처리해주어야 할까?
합승하지 않은 경우는 a~k, a~b 둘중에 0이다.
4. 풀이 - 다익스트라
- cost = dijkstra(s, a) + dijkstra(s, b) 최단 요금을 구해준다.
- 모든 vertex마다 k에 넣고 k를 합승지점이라고 둘 때,
- min(cost, dijkstra(s, k) + dijkstra(k, a) + dijkstra(k, b))를 구하고 갱신한다.
import heapq
import sys
graph = [[]]
INT_MAX = sys.maxsize
def dijkstra(start, end):
global graph
n = len(graph)
pq = []
dist = [INT_MAX] * (n + 1)
dist[start] = 0
heapq.heappush(pq, (0, start))
while pq:
min_dist, min_index = heapq.heappop(pq)
if min_dist != dist[min_index]:
continue
for target_index, target_dist in graph[min_index]:
new_dist = dist[min_index] + target_dist
if new_dist < dist[target_index]:
dist[target_index] = new_dist
heapq.heappush(pq, (new_dist, target_index))
return dist[end]
def solution(n, s, a, b, fares):
global graph
graph = [[] for _ in range(n + 1)]
for fare in fares:
start, end, weight= fare
graph[start].append((end, weight))
graph[end].append((start, weight))
cost = dijkstra(s, a) + dijkstra(s, b)
for k in range(1, n + 1):
if s != k:
cost = min(cost, dijkstra(s, k) + dijkstra(k, a) + dijkstra(k, b))
return cost
5. 다른 풀이 - 플로이드 워셜
- 플로이드 워셜은 시작점이 모든 노드에서 다른 모든 노드까지의 최단경로를 모두 계산한다.
- 각 단계마다 특정한 노드 K를 거쳐가는 경우를 확인하는 알고리즘으로, a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다. min(dist[a][b], dist[a][k] + dist[k][b])
- 그러므로, 탑승 위치를 K로 두면, 플로이드 워셜로 해결하여 최단거리를 구할 수 있다.
import sys
graph = [[]]
INT_MAX = sys.maxsize
def solution(n, s, a, b, fares):
graph = [[INT_MAX] * (n + 1) for _ in range(n + 1)]
cost = INT_MAX
for fare in fares:
start, end, weight= fare
graph[start][end] = weight
graph[end][start] = weight
for i in range(1, n + 1):
graph[i][i] = 0
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for k in range(1, n + 1):
cost = min(cost, graph[s][k] + graph[k][a] + graph[k][b])
return cost
6. 풀이 후 알게된 개념과 소감
- 합승하는 위치를 모든 경우로 다 따져주는 방식으로 접근하는게 포인트다.
- vertex가 작다면 모든 경우를 따지는 것을 고려해보자.
- 중간에 거쳐야 할 지점이 있고, vertex 수가 500미만이라면 플로이드 워셜을 고려해보자.
'Problem Solving' 카테고리의 다른 글
[백준] 2023 : 신기한 소수 / python (0) | 2022.05.23 |
---|---|
[백준] 16236 : 아기 상어 (삼성 SW 역량 테스트) / python (0) | 2022.05.15 |
[백준] 3584 : 가장 가까운 공통 조상 / python (0) | 2022.05.09 |
[백준] 2579 : 계단 오르기 / python (0) | 2022.05.05 |
[백준] 9095 : 1, 2, 3 더하기 / python (0) | 2022.05.02 |