문제 출처
나의 풀이 (실패)
기초적인 설정으로 접근하려 했으나 실패했다.
추가된 조건들을 가지고 그래프를 변형할 줄 알아야 했다.
참고로 그래프 문제에서는 기초적인 설정은 다음과 같다.
1. 여기서는 각 코스를 서로 오고갈 수 있으므로 각 코스별 경로를 trees에 정리해둔다. trees의 각 key값에는 해당 key가 갈 수 있는 경로들이 배열 형태로 저장되어 있게 된다.
2. 각 코스의 거리를 빠르게 가져오기 위해서 weights 배열을 만들어
weights[A경로][B경로] = 가중치 로 사용한다.
function solution(n, paths, gates, summits) {
let weights = Array.from({ length: n + 1 }, () => new Array(n + 1));
let trees = {};
paths.forEach(([start, end, weight]) => {
trees[start] ? trees[start].push(end) : (trees[start] = [end]);
trees[end] ? trees[end].push(start) : (trees[end] = [start]);
weights[start][end] = weight;
weights[start][end] = weight;
});
// ... 로직 작성
}다른 풀이
풀이 1
{1}
일단 graph를 먼저 만들어서 연결관계를 표현한다.
각 지점은 서로 오고 갈 수 있으므로 양방향으로 작성해준다.
{2}
그리고 summit을 돌면서 산봉우리에서 출발하는 경우의 수를 제외해준다.
{3}
q 변수에는 출입구 배열을 할당해준다.
{4}
intensity를 dp 배열에 할당해준다. 이때 최대값으로 초기값을 설정해두고 최소값을 만났을 때만 교체해주는 식으로 진행한다.
{5}
시작 위치를 -1로 초기화해준다.
{6}
bfs를 진행하는데, 변형을 해야 한다.
단순히 각 지점에서 가능한 노드들을 탐색하는 것에서 끝나면 안 된다.
왜냐면 출발지점에서 시작해서 다시 출발지점으로 돌아와야 하기 때문이다.
그래서 while문을 이중으로 사용해서
첫번째 while문에서 등산 코스들을 탐색하며 intensity를 업데이트해주고, 단순히 제거하는 게 아니라 set에 할당해서 set으로 한번 더 탐색해줘야 한다.
{7}
문제의 조건에 따라 intensity가 낮은 순으로 정렬하고 같으면 봉우리 번호가 낮은 순으로 정렬해서 index 0인 요소를 반환하면 된다.
function solution(n, paths, gates, summits) {
// {1}
const graph = new Array(n + 1).fill(null).map((_) => []);
for (let i = 0; i < paths.length; i++) {
const [a, b, w] = paths[i];
graph[a].push([w, b]);
graph[b].push([w, a]);
}
// {2}
for (let summit of summits) {
graph[summit] = [];
}
// {3}
let q = gates;
// {4}
const dp = new Array(n + 1).fill(Infinity);
// {5}
gates.forEach((v) => (dp[v] = -1));
// {6}
while (q.length > 0) {
let set = new Set();
while (q.length > 0) {
const qv = q.pop();
for (let [w, v] of graph[qv]) {
const maxV = Math.max(dp[qv], w);
// 최소일 때만 등산 경로에 추가해준다.
if (dp[v] > maxV) {
dp[v] = maxV;
set.add(v);
}
}
}
q = [...set];
}
// {7}
const res = summits
.map((v) => [v, dp[v]])
.sort((a, b) => {
if (a[1] === b[1]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
return res[0];
}
console.log(
solution(
6,
[
[1, 2, 3],
[2, 3, 5],
[2, 4, 2],
[2, 5, 4],
[3, 4, 4],
[4, 5, 3],
[4, 6, 1],
[5, 6, 1],
],
[1, 3],
[5]
)
);풀이 2
물론 다익스트라가 훨씬 빠르다.
function solution(n, paths, gates, summits) {
// 변수 초기화
const pathMap = {};
const gateMap = {};
const summitMap = {};
summits.sort((a, b) => a - b);
for (const gate of gates) gateMap[gate] = true;
for (const summit of summits) summitMap[summit] = true;
for (const [i, j, w] of paths) {
if (!summitMap[i] && !gateMap[j]) {
pathMap[i] = pathMap[i] || [];
pathMap[i].push([j, w]);
}
if (!summitMap[j] && !gateMap[i]) {
pathMap[j] = pathMap[j] || [];
pathMap[j].push([i, w]);
}
}
// bfs
function bfs(max) {
const visited = {};
const q = [];
// 출발 노드 큐에 넣어주기
for (const gate of gates) {
visited[gate] = true;
q.push(gate);
}
while (q.length) {
const gate = q.shift();
// 경로 없으면 스킵
if (!pathMap[gate]) continue;
for (const [next, w] of pathMap[gate]) {
// 임계치 이상, 방문한 노드면 스킵
if (w > max) continue;
if (visited[next]) continue;
visited[next] = true;
q.push(next);
}
}
for (const summit of summits) {
// 봉우리 방문시 리턴
if (visited[summit]) return summit;
}
return false;
}
// w가 가질수있는 최대값은 10_000_000
let [start, end, mid, summit] = [1, 10 ** 7, 0, n];
// 이분 탐색
while (start <= end) {
mid = Math.floor((start + end) / 2);
const result = bfs(mid);
if (result) {
end = mid - 1;
summit = result;
} else {
start = mid + 1;
}
}
return [summit, start];
}풀이 3 (최소 힙)
class MinHeap {
list = [];
isValid(parentIndex, childIndex) {
return this.list[parentIndex][2] <= this.list[childIndex][2];
}
getParentIndex(i) {
return ((i + 1) >> 1) - 1;
}
getChildIndex(i) {
const left = ((i + 1) << 1) - 1;
return [left, left + 1];
}
push([gate, target, intensity]) {
this.list.push([gate, target, intensity]);
let childIndex = this.size - 1;
let parentIndex = this.getParentIndex(childIndex);
while (parentIndex >= 0 && !this.isValid(parentIndex, childIndex)) {
this.swap(parentIndex, childIndex);
childIndex = parentIndex;
parentIndex = this.getParentIndex(childIndex);
}
}
swap(i, j) {
const tmp = this.list[i];
this.list[i] = this.list[j];
this.list[j] = tmp;
}
pop() {
this.swap(0, this.size - 1);
const value = this.list.pop();
let parentIndex = 0;
let [left, right] = this.getChildIndex(parentIndex);
while (left < this.size) {
let targetIndex =
left === this.size - 1 || this.isValid(left, right) ? left : right;
if (!this.isValid(parentIndex, targetIndex)) {
this.swap(parentIndex, targetIndex);
parentIndex = targetIndex;
[left, right] = this.getChildIndex(parentIndex);
} else {
break;
}
}
return value;
}
get size() {
return this.list.length;
}
}
function solution(n, paths, gates, summits) {
var answer = [];
const nodes = new Array(n)
.fill(null)
.map(() => ({ paths: [], intensityMap: new Map() }));
paths.forEach((path) => {
const [i, j, w] = path;
const nodeI = nodes[i - 1];
const nodeJ = nodes[j - 1];
nodeI.paths.push([j - 1, w]);
nodeJ.paths.push([i - 1, w]);
});
gates.forEach((gate) => (nodes[gate - 1].isGate = true));
summits.forEach((summit) => (nodes[summit - 1].isSummit = true));
let minIntensity = Infinity;
let minSummit = null;
const minHeap = new MinHeap();
for (let i = 0; i < gates.length; i++) {
const gate = gates[i];
minHeap.push([i, gate - 1, 0]);
}
const stack = [];
while (minHeap.size) {
let [_, __, intensity] = minHeap.list[0];
while (minHeap.list[0] && minHeap.list[0][2] === intensity)
stack.push(minHeap.pop());
while (stack.length) {
const [gateIndex, i] = stack.pop();
const gate = gates[gateIndex];
const node = nodes[i];
if (intensity > minIntensity) break;
if (i != gate - 1 && node.isGate) continue;
const nodeIntensity = node.intensityMap.get(gate);
if (nodeIntensity == null || nodeIntensity > intensity) {
node.intensityMap.set(gate, intensity);
if (node.isSummit) {
if (intensity < minIntensity) {
minIntensity = intensity;
minSummit = i + 1;
}
if (intensity === minIntensity && i + 1 < minSummit) {
minSummit = i + 1;
}
continue;
}
for (let [path, pathIntensity] of node.paths) {
if (pathIntensity <= intensity) {
stack.push([gateIndex, path, intensity]);
} else if (pathIntensity < minIntensity)
minHeap.push([gateIndex, path, pathIntensity]);
}
}
}
}
return [minSummit, minIntensity];
}다익스트라(Dijkstra)
그래프에서 출발 지점과 도착 지점 사이의 최단 거리를 구하는 알고리즘이다. 각 정점들을 무한대(INFINITY) 값으로 설정해두고, 출발 지점만 0으로 설정하고 시작한다. 그리고 거리를 기준으로 각 정점을 최소값으로 업데이트하는 방식이다.
일반적으로 단일 정점 간 최단경로 산출 시에 사용한다.
/* pseudocode */
const Dijkstra = (Graph, source) => {
create vertext set Q
for each vertex v in Graph: // 초기화
dist[v] <- Infinity // source에서 v까지의 아직 모르는 길이
add v to Q // 모든 노드는 초기에 Q에 속해 있다 (미방문 집합)
dist[source] <- 0 // source에서 source 까지의 길이 (시작지점은 0으로 시작)
while Q is not empty:
u <- vertext in Q with min dist[u] // 최소 거리를 갖는 정점을 가장 먼저 선택
remove u from Q
for each neighbor v of u: // v는 여전히 Q에 있다
alt <- dist[u] + length(u, v) // v 까지의 더 짧은 경로를 찾았을 때
if alt < dist[v]:
dist[v] <- alt
return dist[]
}Floyd-Warshall
동적계획법을 사용해서 그래프에서 가능한 모든 정점 쌍에 대해 최단 거리를 구하는 알고리즘이다. 음의 가중치가 있어도 사용가능하며, 많은 수의 간선으로 이루어져 있는 밀집 그래프에 사용하기 좋다.
/* pseudocode */
const floydWarshall = () => {
let dist be a |V| x |V| array of
minimum distance initialized to = (Infinity)
for each edge (u, v)
dist[u][v] <- w(u, v) // 변 (u, v)의 가중치
for each vertext v
dist[v][v] <- 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] <- dist[i][k] + dist[k][j]
end if
}동적계획법을 기반으로,
dis[c][d] : c에서 d로 가는 최단 경로와
dis[c][b] + dis[b][d] = c에서 b로 갔다가, b에서 d로 가는 최단 경로의 합을 비교해서 더 작은 걸로 계속 업데이트해나가는 방식이다.
다익스트라와 플로이드 워샬을 구현하면 다음과 같다.
function ShortestPath() {
this.edges = {};
}
// 정점 추가
ShortestPath.prototype.addVertex = function (vertex) {
this.edges[vertex] = {};
};
// 간선 추가
ShortestPath.prototype.addEdge = function (srcVertex, dstVertex, weight) {
this.edges[srcVertex][dstVertex] = weight;
};
// 최단 거리 노드 탐색
ShortestPath.prototype._extractMin = function (queue, dist) {
let minDistance = Number.POSITIVE_INFINITY;
let minVertex = null;
for (let vertex in queue) {
if (dist[vertex] <= minDistance) {
minDistance = dist[vertex];
minVertex = vertex;
}
}
return minVertex;
};
// 다익스트라 최단 경로 검색
ShortestPath.prototype.dijkstra = function (start) {
let queue = {};
let dist = {};
for (let vertex in this.edges) {
dist[vertex] = Number.POSITIVE_INFINITY;
queue[vertex] = this.edges[vertex];
}
dist[start] = 0;
while (Object.keys(queue).length != 0) {
// 출발지점을 0으로 했으므로 처음엔 start vertex가 u에 저장된다.
let u = this._extractMin(queue, dist);
delete queue[u];
for (let neighbor in this.edges[u]) {
let alt = dist[u] + this.edges[u][neighbor];
// 최소 비용 + 현재노드까지의 거리가 최소비용보다 작으면 업데이트
if (alt < dist[neighbor]) dist[neighbor] = alt;
}
}
// 유향 그래프면 갈 수 없는 정점들은 제거해준다.
for (let vertex in this.edges) {
if (dist[vertex] === Number.POSITIVE_INFINITY) delete dist[vertex];
}
return dist;
};
// 플로이드 워셜 최단 경로 탐색
ShortestPath.prototype.floydWarshall = function () {
let dist = {};
// 초기화
for (let srcVertex in this.edges) {
dist[srcVertex] = {};
for (let dstVertex in this.edges) {
if (srcVertex === dstVertex) dist[srcVertex][dstVertex] = 0;
else dist[srcVertex][dstVertex] = Number.POSITIVE_INFINITY;
}
}
for (let srcVertex in this.edges) {
for (let dstVertex in this.edges[srcVertex]) {
dist[srcVertex][dstVertex] = this.edges[srcVertex][dstVertex];
}
}
// 최단 경로 업데이트
for (let minVertex in this.edges) {
for (let srcVertex in this.edges) {
for (let dstVertex in this.edges) {
dist[srcVertex][dstVertex] = Math.min(
dist[srcVertex][dstVertex],
dist[srcVertex][minVertex] + dist[minVertex][dstVertex]
);
}
}
}
// 유형 그래프면 갈 수 없는 경로들 제거
for (let srcVertex in this.edges) {
for (let dstVertex in this.edges) {
if (dist[srcVertex][dstVertex] === Number.POSITIVE_INFINITY) {
delete dist[srcVertex][dstVertex];
}
}
}
return dist;
};
let path = new ShortestPath();
path.addVertex("A");
path.addVertex("B");
path.addVertex("C");
path.addVertex("D");
path.addVertex("E");
path.addEdge("A", "B", 10);
path.addEdge("A", "C", 3);
path.addEdge("B", "C", 1);
path.addEdge("B", "D", 2);
path.addEdge("C", "B", 4);
path.addEdge("C", "D", 8);
path.addEdge("C", "E", 2);
path.addEdge("D", "E", 7);
path.addEdge("E", "D", 9);
console.log(path);
/* output
ShortestPath {
edges: {
A: { B: 10, C: 3 },
B: { C: 1, D: 2 },
C: { B: 4, D: 8, E: 2 },
D: { E: 7 },
E: { D: 9 }
}
}
*/
console.log(path.dijkstra("A")); // { A: 0, B: 7, C: 3, D: 9, E: 5 }
console.log(path.dijkstra("B")); // { B: 0, C: 1, D: 2, E: 3 }
console.log(path.dijkstra("C")); // { B: 4, C: 0, D: 6, E: 2 }
console.log(path.floydWarshall());
/*
{
A: { A: 0, B: 7, C: 3, D: 9, E: 5 },
B: { B: 0, C: 1, D: 2, E: 3 },
C: { B: 4, C: 0, D: 6, E: 2 },
D: { D: 0, E: 7 },
E: { D: 9, E: 0 }
}
*/
Heap
힙은 수의 집합에서 가장 작은 수나 가장 큰 수만 자주 가져다 쓸 때 유용한 자료구조이다.
예를 들어 숫자로 구성된 배열이 있을 때, 최소값을 찾으려면 for loop를 진행하는 게 일반적이다. 그럼 시간복잡도는 O(N)이 된다. 이때 힙을 사용하면 O(logN)으로 줄일 수 있다.
(최대값 혹은 최소값을 빠르게 찾기 위해 완전이진트리 형태로 연산을 수행하는 자료구조. 완전이진트리는 배열로 표현할 수 있다. => 현재 노드(index): N, 부모노드: (N-1) / 2, 왼쪽자식노드: (N*2) + 1, 오른쪽 자식 노드: (N*2) + 2 (결국, 노드가 2^n - 1 형태로 점진적으로 증가하기 때문에 가능하다))
힙은 완전이진트리를 사용한다.
항상 자식은 2개. leaf의 가장 왼쪽부터 채운다.
최소힙과 최대힙은 유사하다.
- 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드의 값보다, 작거나 같은 완전 이진 트리
- 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드의 값보다, 크거나 같은 완전 이진 트리
최소힙을 살펴보면,
- 루트에 최소값을 배치, 자식으로 자신보다 작은 노드들을 완전이진트리에 배치시킨다.
- 트리 형태의 노드들을 배열로 생각하면 되는데, 왼쪽 자식은
자신의 index * 2, 오른쪽 자식은자신의 index * 2 + 1이 된다. 반대로 부모의 index는자신의 index / 2로 구할 수 있다.
최소 힙을 이렇게 배열한 상태로, 노드들을 삽입하는데
leaf 노드에서부터 비교하면서 삽입할 노드가 현재 노드보다 크면 멈춘다. (노드를 삽입하면 무조건 전부 비교해주면서 올바른 위치를 찾아준다.)
최소 힙을 구현하면 다음과 같다. (최대 힙은 bubbleUp, bubbleDown 메서드에서의 부등호가 반대로 바뀐다는 점을 제외하고는 기본적인 로직은 동일하다.)
function Heap() {
this.items = [];
}
// 배열 내 두 요소 위치 변경
Heap.prototype.swap = function (fidx, sidx) {
let temp = this.items[fidx];
this.items[fidx] = this.items[sidx];
this.items[sidx] = temp;
};
// 부모 노드 위치 반환
Heap.prototype.parentIndex = function (idx) {
return Math.floor((idx - 1) / 2);
};
// 왼쪽 자식 노드 위치 반환
Heap.prototype.leftChildIndex = function (idx) {
return idx * 2 + 1;
};
// 오른쪽 자식 노드 위치 반환
Heap.prototype.rightChildIndex = function (idx) {
return idx * 2 + 2;
};
// 부모 노드 요소 값 반환
Heap.prototype.parent = function (idx) {
return this.items[this.parentIndex(idx)];
};
// 왼쪽 자식 노드 요소 값 반환
Heap.prototype.leftChild = function (idx) {
return this.items[this.leftChildIndex(idx)];
};
// 오른쪽 자식 노드 요소 값 반환
Heap.prototype.rightChild = function (idx) {
return this.items[this.rightChildIndex(idx)];
};
// 현재 정렬된 최소/최대 요소값 반환 (this.root)
Heap.prototype.peek = function () {
return this.items[0];
};
// 현재 배열 크기 반환
Heap.prototype.size = function () {
return this.items.length;
};
// 신규 노드 추가
Heap.prototype.insert = function (item) {
this.items[this.size()] = item;
this.bubbleUp(); // 노드를 추가함과 동시에 정렬
};
// 추가된 노드 위치 정렬
Heap.prototype.bubbleUp = function () {
let currentIndex = this.size() - 1;
// 부모 노드가 존재하고, 부모 노드가 나보다 크면,
while (
this.parent(currentIndex) &&
this.parent(currentIndex) > this.items[currentIndex]
// 최대 힙이면 this.parent(currentIndex) < this.items[currentIndex]
) {
this.swap(this.parentIndex(currentIndex), currentIndex);
currentIndex = this.parentIndex(currentIndex);
}
};
// root 노드 반환 및 삭제 (루트 자리에 항상 최소값이 위치한다.)
Heap.prototype.extract = function () {
let item = this.items[0];
// 루토 노드를 삭제할 때 인접 노드로 채우는 게 아니라 제일 뒤에 있는 노드를 이 자리에 넣고 정렬해준다.
this.items[0] = this.items[this.size() - 1];
this.items.pop();
this.bubbleDown();
return item;
};
// 대체된 root 노드 위치를 기준으로 정렬
Heap.prototype.bubbleDown = function () {
let currentIndex = 0;
while (
// 왼쪽 자식 노드가 있고, 오른쪽 혹은 왼쪽 자식노드가 나보다 작으면
this.leftChild(currentIndex) &&
// 최대 힙이면
// this.leftChild(currentIndex) > this.items[currentIndex]
// this.rightChild(currentIndex) > this.items[currentIndex]
(this.leftChild(currentIndex) < this.items[currentIndex] ||
this.rightChild(currentIndex) < this.items[currentIndex])
) {
// 왼쪽 자식부터 시작
let childIndex = this.leftChildIndex(currentIndex);
if (
// 만약 오른쪽 자식 노드가 있고 그게 왼쪽 자식 노드보다 작으면
this.rightChild(currentIndex) &&
// 최대 힙이면 this.rightChild(currentIndex) > this.items[childIndex]
this.rightChild(currentIndex) < this.items[childIndex]
) {
// 오른쪽 자식노드 index를 childIndex 변수에 저장
childIndex = this.rightChildIndex(currentIndex);
}
this.swap(childIndex, currentIndex);
currentIndex = childIndex;
}
};
let minHeap = new Heap();
minHeap.insert(90);
minHeap.insert(15);
minHeap.insert(10);
minHeap.insert(7);
minHeap.insert(12);
minHeap.insert(2);
minHeap.insert(8);
minHeap.insert(3);
console.log(minHeap);
/*
Heap {
items: [
2, 3, 7, 10,
12, 15, 8, 90
]
}
*/
console.log(minHeap.extract());
console.log(minHeap);
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
console.log(minHeap.extract());
참고
https://medium.com/@wooleejaan