XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.
등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.
등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity
라고 부르기로 합니다.
당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
당신은 이러한 규칙을 지키면서 intensity
가 최소가 되도록 등산코스를 정하려고 합니다.
XX산의 지점 수 n
, 각 등산로의 정보를 담은 2차원 정수 배열 paths
, 출입구들의 번호가 담긴 정수 배열 gates
, 산봉우리들의 번호가 담긴 정수 배열 summits
가 매개변수로 주어집니다. 이때, intensity
가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity
의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity
가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.
제한사항
n
≤ 50,000n
- 1 ≤ paths
의 길이 ≤ 200,000paths
의 원소는 [i, j, w]
형태입니다.i
번 지점과 j
번 지점을 연결하는 등산로가 있다는 뜻입니다.w
는 두 지점 사이를 이동하는 데 걸리는 시간입니다.i
< j
≤ n
w
≤ 10,000,000gates
의 길이 ≤ n
gates
의 원소 ≤ n
gates
의 원소는 해당 지점이 출입구임을 나타냅니다.summits
의 길이 ≤ nsummits
의 원소 ≤ nsummits
의 원소는 해당 지점이 산봉우리임을 나타냅니다.gates
와 summits
에 등장하지 않은 지점은 모두 쉼터입니다.[산봉우리의 번호, intensity의 최솟값]
순서여야 합니다.function solution(n, paths, gates, summits) {
const MAX_INTENSITY = 10000001;
const answer = [n, MAX_INTENSITY];
const hikingCourses = Array.from({length: n+1}, () => []);
paths.forEach(([start, end, weight]) => {
hikingCourses[start].push([end, weight]);
hikingCourses[end].push([start, weight]);
});
const isSummits = Array.from({length: n+1}, () => false);
summits.forEach((summit) => {
isSummits[summit] = true;
});
summits.sort((a, b) => a - b);
const dijkstra = () => {
const priorityQueue = new PriorityQueue();
const intensities = Array(n+1).fill(MAX_INTENSITY);
gates.forEach((gate) => {
priorityQueue.enqueue(gate, 0);
intensities[gate] = 0;
});
while(priorityQueue.values.length) {
const node = priorityQueue.dequeue();
const vertex = node.val;
const time = node.priority;
if (intensities[vertex] < time || isSummits[vertex]) {
continue;
}
const adjacencyList = hikingCourses[vertex];
const listLength = adjacencyList.length;
for (let i = 0; i < listLength; i++) {
const [nextVertex, nextTime] = adjacencyList[i];
if (intensities[nextVertex] > Math.max(intensities[vertex], nextTime)) {
intensities[nextVertex] = Math.max(intensities[vertex], nextTime);
priorityQueue.enqueue(nextVertex, intensities[nextVertex]);
}
}
}
return intensities;
}
const intensities = dijkstra();
summits.forEach((summit) => {
if (intensities[summit] < answer[1]) {
answer[0] = summit;
answer[1] = intensities[summit];
}
});
return answer;
}
class Node {
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(val, priority) {
let newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp() {
let idx = this.values.length - 1;
const element = this.values[idx];
let parentIdx;
let parent;
while(idx > 0) {
parentIdx = Math.floor((idx - 1)/2);
parent = this.values[parentIdx];
if (element.priority >= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
dequeue() {
const min = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return min;
}
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
let leftChildIdx;
let rightChildIdx;
let leftChild;
let rightChild;
let swap;
while(true) {
leftChildIdx = 2 * idx + 1;
rightChildIdx = 2 * idx + 2;
swap = null;
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
if (leftChild.priority < element.priority) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if (
(swap === null && rightChild.priority < element.priority) ||
(swap !== null && rightChild.priority < leftChild.priority)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}
n
, and edges will have varying distances or lengths.Begin | End | Weight |
---|---|---|
1 | 2 | 5 |
2 | 3 | 6 |
3 | 4 | 2 |
1 | 3 | 15 |
The distances to all nodes in increasing node order, omitting the starting node, are 5 11 13 -1.
n
: the number of nodes in the graphedges
: a 2D array of integers where each edges[i]
consists of three integers x
, y
, and r
that represent the start and end nodes of an edge, followed by its lengths
: the start node numbern
<= 3000x
, y
, x
<= n
r
<= 10^5function shortestReach(n, edges, s) {
const graph = Array.from({length: n+1}, () => []);
const MAX = 100001;
edges.forEach(([begin, end, weight]) => {
graph[begin].push([end, weight]);
graph[end].push([begin, weight]);
});
const dijkstra = () => {
const priorityQueue = new PriorityQueue();
const distances = Array(n+1).fill(MAX);
priorityQueue.enqueue(s, 0);
distances[s] = 0;
while (priorityQueue.values.length) {
const node = priorityQueue.dequeue();
const currNode = node.val;
const currDistance = node.priority;
if (distances[currNode] < currDistance) {
continue;
}
const adjacencyList = graph[currNode];
const listLength = adjacencyList.length;
for (let i = 0; i < listLength; i++) {
const [nextNode, nextDistance] = adjacencyList[i];
const candidateDistance = distances[currNode] + nextDistance;
if (distances[nextNode] > candidateDistance) {
distances[nextNode] = candidateDistance;
priorityQueue.enqueue(nextNode, candidateDistance);
}
}
}
return distances;
}
let distances = dijkstra();
const result = [];
distances.forEach((distance, index) => {
if (index === 0 || distance === 0) {
return;
}
if (distance === MAX) {
result.push(-1);
return;
}
result.push(distance);
});
return result;
}
class PriorityQueue {
constructor(){
this.values = [];
}
enqueue(val, priority){
let newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp(){
let idx = this.values.length - 1;
const element = this.values[idx];
while(idx > 0){
let parentIdx = Math.floor((idx - 1)/2);
let parent = this.values[parentIdx];
if(element.priority >= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
dequeue(){
const min = this.values[0];
const end = this.values.pop();
if(this.values.length > 0){
this.values[0] = end;
this.sinkDown();
}
return min;
}
sinkDown(){
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while(true){
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild,rightChild;
let swap = null;
if(leftChildIdx < length){
leftChild = this.values[leftChildIdx];
if(leftChild.priority < element.priority) {
swap = leftChildIdx;
}
}
if(rightChildIdx < length){
rightChild = this.values[rightChildIdx];
if(
(swap === null && rightChild.priority < element.priority) ||
(swap !== null && rightChild.priority < leftChild.priority)
) {
swap = rightChildIdx;
}
}
if(swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}
class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}
위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N
, 각 마을을 연결하는 도로의 정보 road
, 음식 배달이 가능한 시간 K
가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
N
은 1 이상 50 이하의 자연수입니다.road
의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.road
의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.road
는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.K
는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.K
이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.function solution(N, road, K) {
const roadMap = Array.from({length: N+1}, () => []);
road.forEach(([start, end, weight]) => {
roadMap[start].push([end, weight]);
roadMap[end].push([start, weight]);
});
const dijkstra = () => {
const priorityQueue = new PriorityQueue();
const MAX_TIME = 500000;
const deliveryTime = Array(N+1).fill(MAX_TIME);
priorityQueue.enqueue(1, 0);
deliveryTime[1] = 0;
while(priorityQueue.values.length) {
const node = priorityQueue.dequeue();
const village = node.val;
const time = node.priority;
const neighborList = roadMap[village];
const neighborCount = neighborList.length;
for (let i = 0; i < neighborCount; i++) {
const [nextVillage, nextTime] = neighborList[i];
const totalTime = deliveryTime[village] + nextTime;
if (totalTime > K) {
continue;
}
if (deliveryTime[nextVillage] > totalTime) {
deliveryTime[nextVillage] = totalTime;
priorityQueue.enqueue(nextVillage, totalTime);
}
}
}
return deliveryTime.filter((time) => time < MAX_TIME).length;
};
const deliverableVillages = dijkstra();
return deliverableVillages;
}
class PriorityQueue {
constructor(){
this.values = [];
}
enqueue(val, priority){
let newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp(){
let idx = this.values.length - 1;
const element = this.values[idx];
while(idx > 0){
let parentIdx = Math.floor((idx - 1)/2);
let parent = this.values[parentIdx];
if(element.priority >= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
dequeue(){
const min = this.values[0];
const end = this.values.pop();
if(this.values.length > 0){
this.values[0] = end;
this.sinkDown();
}
return min;
}
sinkDown(){
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while(true){
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild,rightChild;
let swap = null;
if(leftChildIdx < length){
leftChild = this.values[leftChildIdx];
if(leftChild.priority < element.priority) {
swap = leftChildIdx;
}
}
if(rightChildIdx < length){
rightChild = this.values[rightChildIdx];
if(
(swap === null && rightChild.priority < element.priority) ||
(swap !== null && rightChild.priority < leftChild.priority)
) {
swap = rightChildIdx;
}
}
if(swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}
class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}