배운 코드
class Heap {
constructor() {
this.heap = [];
}
getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);
peek = () => this.heap[0];
insert = (key, value) => {
const node = { key, value };
this.heap.push(node);
this.heapifyUp();
};
heapifyUp = () => {
let index = this.heap.length - 1;
const lastInsertedNode = this.heap[index];
while (index > 0) {
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex].key > lastInsertedNode.key) {
this.heap[index] = this.heap[parentIndex];
index = parentIndex;
} else break;
}
this.heap[index] = lastInsertedNode;
};
remove = () => {
const count = this.heap.length;
const rootNode = this.heap[0];
if (count <= 0) return undefined;
if (count === 1) this.heap = [];
else {
this.heap[0] = this.heap.pop();
this.heapifyDown();
}
return rootNode;
};
heapifyDown = () => {
let index = 0;
const count = this.heap.length;
const rootNode = this.heap[index];
while (this.getLeftChildIndex(index) < count) {
const leftChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
const smallerChildIndex =
rightChildIndex < count &&
this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
? rightChildIndex
: leftChildIndex;
if (this.heap[smallerChildIndex].key <= rootNode.key) {
this.heap[index] = this.heap[smallerChildIndex];
index = smallerChildIndex;
} else break;
}
this.heap[index] = rootNode;
};
}
class PriorityQueue extends Heap {
constructor() {
super();
}
enqueue = (priority, value) => this.insert(priority, value);
dequeue = () => this.remove();
isEmpty = () => this.heap.length <= 0;
}
function solution(n, s, a, b, fares) {
let answer = Number.MAX_SAFE_INTEGER
// 동승하는 구간은 브루투 포스로 찾는다. 모든 지점
const graph = [...new Array(n)].map(()=>[...new Array(n)].map(()=>Number.MAX_SAFE_INTEGER));
fares.forEach(([s,f,v])=>{
graph[s-1][f-1] = v;
graph[f-1][s-1] = v;
})
for(let i=0;i<n;i++){
const [p1,p2] = dijkstra(graph,n,s-1,i,0)
const [q1,q2] = dijkstra(graph,n,i,a-1,b-1)
answer = Math.min(answer,p1+q1+q2);
}
return answer;
function dijkstra(graph,n,s,f1,f2){
const dist = [...new Array(n)].map(()=>Number.MAX_SAFE_INTEGER);
const pq = new PriorityQueue();
pq.enqueue(0,s);
dist[s] = 0;
while(!pq.isEmpty()){
const {key:cost,value:node} = pq.dequeue();
for(let i=0;i<n;i++){
const nextCost = dist[node] + graph[node][i];
if(nextCost < dist[i]){
// 작으니깐 최단 경로 갱신 !
// 갱신 했다면 큐에 넣는다.
dist[i] = nextCost
pq.enqueue(nextCost, i);
}
}
}
return [dist[f1],dist[f2]];
}
}우선순위 큐 js
class Heap {
constructor(type) {
this.heap = [];
this.type = type;
}
static findLeftChild(parent) {
return parent * 2 + 1;
}
static findRightChild(parent) {
return parent * 2 + 2;
}
static findParent(child) {
return Math.floor((child - 1) / 2);
}
peek() {
return this.heap[0];
}
insert(key, value) {
// 가장 마지막에 넣고
// 부모와 비교하며 히피파이 업 시킨다.
this.heap.push({ key, value });
if (this.type === "MAX") {
this.maxHeapifyUp();
return;
}
if (this.type === "MIN") {
this.minHeapifyUp();
return;
}
}
remove() {
// rootNode를 내보내고
// 마지막 요소를 부모로 가져와 히파파이 다운 시킨다.
if (this.heap.length <= 0) {
return null;
}
if (this.heap.length === 1) {
return this.heap.pop();
}
const front = this.heap[0];
this.heap[0] = this.heap.pop();
if (this.type === "MAX") {
this.maxHeapifyDown();
return front;
}
if (this.type === "MIN") {
this.minHeapifyDown();
return front;
}
}
maxHeapifyUp() {
// 가장 마지막 요소를 히피파이 업한다.
// 부모요소보다 큰 지 작은 지를 판단한다.
let cur = this.heap.length - 1;
const targetElement = this.heap[cur];
while (cur > 0) {
const parent = Heap.findParent(cur);
const parentElement = this.heap[parent];
if (parentElement.key < targetElement.key) {
this.heap[cur] = parentElement;
cur = parent;
} else {
break;
}
}
this.heap[cur] = targetElement;
}
minHeapifyUp() {
// 가장 마지막 요소를 히피파이 업한다.
// 부모요소보다 큰 지 작은 지를 판단한다.
let cur = this.heap.length - 1;
const targetElement = this.heap[cur];
while (cur > 0) {
const parent = Heap.findParent(cur);
const parentElement = this.heap[parent];
if (parentElement.key > targetElement.key) {
this.heap[cur] = parentElement;
cur = parent;
} else {
break;
}
}
this.heap[cur] = targetElement;
}
maxHeapifyDown() {
// 루트 요소를 히피파이 다운한다.
let cur = 0;
const rootNode = this.heap[0];
while (cur < this.heap.length) {
const left = Heap.findLeftChild(cur);
const right = Heap.findRightChild(cur);
if (this.heap[left] === undefined) {
break;
}
let target;
if (this.heap[right] === undefined) {
// 좌측이랑 교체
target = left;
} else {
target = this.heap[left].key < this.heap[right].key ? right : left;
}
if (this.heap[target].key > rootNode.key) {
// 교체
this.heap[cur] = this.heap[target];
cur = target;
} else {
break;
}
}
this.heap[cur] = rootNode;
}
minHeapifyDown() {
// 루트 요소를 히피파이 다운한다.
let cur = 0;
const rootNode = this.heap[0];
while (cur < this.heap.length) {
const left = Heap.findLeftChild(cur);
const right = Heap.findRightChild(cur);
if (this.heap[left] === undefined) {
break;
}
let target;
if (this.heap[right] === undefined) {
// 좌측이랑 교체
target = left;
} else {
target = this.heap[left].key > this.heap[right].key ? right : left;
}
if (this.heap[target].key < rootNode.key) {
// 교체
this.heap[cur] = this.heap[target];
cur = target;
} else {
break;
}
}
this.heap[cur] = rootNode;
}
}
class PQ extends Heap {
constructor(type) {
super(type);
}
enqueue(key, value) {
return this.insert(key, value);
}
dequeue() {
return this.remove();
}
isEmpty() {
return this.heap.length <= 0;
}
}다익스트라 (기준은 시작점으로 부터)
시작 지점으로 부터 모든 지점 까지의 최단 경로를 구한다.
function dijkstra(graph, n, s) {
// 그래프, 노드 갯수, 시작 지점
const dist = [...new Array(n)].map(() => Number.MAX_SAFE_INTEGER);
const pq = new PQ("MIN");
dist[s] = 0;
pq.enqueue(0, s);
while (!pq.isEmpty()) {
const { key, value } = pq.dequeue();
for (let i = 0; i < n; i++) {
// 지금까지 i로 가는 경로 보다
// 큐에서 나온 지점을 들렸다가는게 더 빠르다면 교체한다.
if (dist[i] > dist[value] + graph[value][i]) {
dist[i] = dist[value] + graph[value][i];
// 간선의 값을 키로 넣지말고, 갱신되는 최단 경로 비용 값을 키로 넣자.
// 우선순위가 낮은게 더 먼저 실행되도록 하기 위해 경로를 넣게 되면 최단 경로가 아닌 연결된 경로의 비용으로 비교하게 되서 시간이 오래걸린다.
pq.enqueue(dist[i], i);
}
}
}
return dist;
}플로이드 와샬 알고리즘 (기준은 교차점)
다익스트라는 1차원 배열을 두고, 한 점에서 가는 모든 정점으로 최단 경로를 구했다. 거쳐가는 노드가 생길 때 마다, 이걸 거쳐가는 게 더 빠른지 아님 지금까지의 최단경로가 빠른지를 비교해서 갱신하거나 하지 않게된다.
플로이드 와샬 알고리즘은 거쳐가는 노드가 중심이된다. 어떤 걸 거쳐가는 지를 중심으로 갱신한다.
모든 정점에서 모든 정점으로의 최단 경로를 구한다.
만약 정점이 4개라면,
1번 정점을 거쳐갈 때가 빠른지 직접 갈때가 빠른지를 모든 정점 대상으로 비교한다. (이렇게 하면 더 빠른 경우는 1번 정점을 거쳐갈 것이고, 아니라면 직접 가게 된다)
2번 정점을 거쳐갈 때가 빠른지 직접 갈때가 빠른지를 모든 정점 대상으로 비교한다. (이렇게 하면 더 빠른 경우 2번 정점을 거치게되고, 만약 1번 정점을 거친 경우가 2번 정점을 거치게 되어 더 빠르다면 이 경로 값이 반영된다.)
... 모든 정점을 대상으로 시행하면된다.
function solution(n, s, a, b, fares) {
let answer = Number.MAX_SAFE_INTEGER
// 동승하는 구간은 브루투 포스로 찾는다. 모든 지점
const graph = [...new Array(n)].map(()=>[...new Array(n)].map(()=>Number.MAX_SAFE_INTEGER));
for(let i=0;i<n;i++){
graph[i][i] = 0;
}
fares.forEach(([s,f,v])=>{
graph[s-1][f-1] = v;
graph[f-1][s-1] = v;
})
/*
가장 바깥 쪽, 그니깐 가장 기준이 되는 것이 중간점이어야 한다.
시작 점을 기준으로 돌게되면 나중에 시작하는 점에서 앞 점을 참조할 때 그 때의 이후 정점을 참조할 때 그 점이 최단 경로가 아닐 수 있다.
*/
for(let mid=0;mid<n;mid++){
for(let start =0;start<n;start++){
for(let finish=0;finish<n;finish++){
if(start !== mid && mid !== finish){
graph[start][finish] = Math.min(graph[start][finish],graph[start][mid] + graph[mid][finish])
}
}
}
}
for(let i=0;i<n;i++){
const hap = graph[s-1][i] + graph[i][a-1] + graph[i][b-1]
answer = Math.min(answer,hap)
}
return answer;
}Ref
다익스트라 구현해본적이 너무 옛날이라 강의 보고 코드를 따라 쳐봄
Frontend Ninja