## 🌟 문제
[코딩테스트 연습 - 합승 택시 요금 \| 프로그래머스 스쿨](https://school.programmers.co.kr/learn/courses/30/lessons/72413)
출발지 s에서 두 사람이 각각 목적지 a, b로 이동한다.
특정 지점까지 택시 합승이 가능하고, 합승이 종료된 이후에는 따로 이동한다.
이 때 전체 요즘의 최솟값을 구하는 문제
그래프는 무방향이고, 가중치가 있다.
## 🌟 풀이
### 아이디어 도출
무방향이고 가중치가 있는 그래프에서 최단거리를 구하는 문제이다! 특정 시작점이 존재하는 것을 보니 아무리 봐도 [[다익스트라 알고리즘]]을 사용하는 문제이다.
핵심은 어디까지 합승을 하느냐의 문제이다.
합승을 끝내는 지점을 c라고 했을 때, 전체 비용은 아래와 같이 표현할 수 있다.
```javascript
// (s → c) + (c → a) + (c → b)
dist(s, c) + dist(c, a) + dist(c, b)
```
합승을 하지 않아도 괜찮기 때문에 시작점이 `c`가 되어도 된다.
즉 모든 노드 `c`를 합승 분기점 후보로 두고, 위 식의 최솟값을 구하면 되는 문제였다.
### 알고리즘 결정
처음에는 [[다익스트라 알고리즘]]을 쓰면 되겠다고 생각했지만 합승 분기점이라는 또 다른 출발점이 생겼고, 이 출발점 후보는 모든 노드이기에 [[플로이드-워셜 알고리즘]]을 써야 하나? 하는 생각도 들었다.
하지만 약간 생각을 바꾸면 [[다익스트라 알고리즘]]만으로도 문제를 풀 수 있고, 이 편이 더 효율적이다.
> 다익스트라 3번
- `distS = dijkstra(s)` : `s`에서 출발하는 경로의 최단거리
- `distA = dijkstra(a)` : `a`에서 출발하는 경로의 최단거리
- `distB = dijkstra(b)` : `b`에서 출발하는 경로의 최단거리
어차피 무방향이기 때문에 `c → a` 경로나 `a → c` 경로나 비용은 동일하다. 따라서 `a`, `b`에서 출발하는 경로의 최단 거리를 구한 다음에, 모든 `c` 후보를 검토하면서 최단 거리를 구해줬다.
```javascript
let answer = Infinity;
for (let c = 1; c <= n; c++) {
answer = Math.min(answer, distS[c] + distA[c] + distB[c]);
}
```
## 전체 코드
```javascript
class Heap {
constructor(compare) {
this.heap = [];
this.compare = compare;
}
size() {
return this.heap.length;
}
// 새로운 원소를 힙에 추가
// 가장 끝에 넣고 제자리를 찾아서 올려준다.
push(value) {
this.heap.push(value);
this.siftUp(this.heap.length - 1);
}
// root를 뺀다.
// 가장 끝 값을 root로 올리고, 제자리를 찾아 내린다.
pop() {
if (this.size() <= 0) return null; // NOTE : 명시적으로 값을 반환해주는 쪽이 더 좋음
if (this.size() === 1) return this.heap.pop(); // NOTE : 이거 잊지 맙시다.
const ret = this.heap[0];
this.heap[0] = this.heap.pop();
this.siftDown(0);
return ret;
}
// push와 함께 사용
// 제자리 찾아서 올라가는 단계
siftUp(idx) {
// heap 규칙에 어긋난다면 swap으로 올려준다.
// root이거나 heap 규칙에 잘 맞는다면 shiftUp 중단
while (idx > 0) {
const parent = Math.floor((idx - 1) / 2);
if (this.compare(this.heap[idx], this.heap[parent])) {
this.swap(idx, parent);
idx = parent;
} else {
break;
}
}
}
// pop과 함께 사용
// 제자리 찾아서 내려가는 단계
siftDown(idx) {
while (true) {
const leftChild = idx * 2 + 1;
const rightChild = idx * 2 + 2;
let targetChild;
if (leftChild >= this.size()) break;
else if (rightChild >= this.size()) targetChild = leftChild;
else
targetChild = this.compare(this.heap[leftChild], this.heap[rightChild])
? leftChild
: rightChild;
if (this.compare(this.heap[targetChild], this.heap[idx])) {
this.swap(targetChild, idx);
idx = targetChild;
} else {
break;
}
}
}
// a 인덱스와 b인덱스의 값을 스왑
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
}
function solution(n, s, a, b, fares) {
// 0. 다익스트라에 필요한 데이터 준비하기
// adj: 인접 리스트 (원소: [v, w])
const adj = Array.from({ length: n + 1 }, () => []);
for (const [c, d, f] of fares) {
adj[c].push([d, f]);
adj[d].push([c, f]);
}
// 1. 다익스트라 구현
// start: 경로를 계산할 시작 지점.
// 시작 지점부터 다른 전체 노드까지의 각 최단 경로를 반환한다.
function dijkstra(start) {
// 0) 초기 설정
const dist = new Array(n + 1).fill(Infinity);
dist[start] = 0;
const minHeap = new Heap(([c1, v1], [c2, v2]) => c1 < c2);
minHeap.push([0, start]);
// 1) minHeap이 빌 때까지 반복한다.
while (minHeap.size() > 0) {
const [cost, u] = minHeap.pop();
// NOTE : dist 정보와 cost 정보가 다르다면 구버전 정보이므로 넘어간다. (이미 처리한 노드임을 의미)
if (cost !== dist[u]) continue;
// 2) u의 간선들을 모두 탐색한다.
for (const [v, w] of adj[u]) {
// 3) v로 가는데 걸리는 비용의 최솟값을 업데이트한다.
const nextCost = cost + w;
if (nextCost < dist[v]) {
dist[v] = nextCost;
minHeap.push([nextCost, v]);
}
}
}
return dist;
}
// 2. S에서 출발하는 경로의 최단거리
const distS = dijkstra(s);
// 3. A에서 출발하는 경로의 최단거리 (중간지점 - A까지의 거리 계산용)
const distA = dijkstra(a);
// 4. B에서 출발하는 경로의 최단거리 (중간지점 - B까지의 거리 계산용)
const distB = dijkstra(b);
// 5. 모든 중간지점 c를 확인하면서 총 비용이 최소가 되는 c를 찾는다.
// 합승을 안해도 되기 때문에 시작지점도 확인한다.
let answer = Infinity;
for (let c = 1; c <= n; c++) {
answer = Math.min(answer, distS[c] + distA[c] + distB[c]);
}
return answer;
}
```