[다익스트라 알고리즘] 배달

Problem. 배달

---

Link.

https://school.programmers.co.kr/learn/courses/30/lessons/12978?language=javascript

프로그래머스

 

---

Problem.

N개의 마을로 이루어진 나라가 있습니다.

이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어있습니다.

각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다.

도로를 지날 때 걸리는 시간은 도로별로 다릅니다.

현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다.

각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다.

다음은 N = 5, K = 3인 경우의 예시입니다.

N = 5, K = 3

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다.

그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다.

따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.

 

마을의 개수는 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성하시오.

 

제한사항

1. 마을의 개수 N은 1 이상 50 이하의 자연수입니다.

2. road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.

3. road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.

4. road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.

  - a, b는 도로가 연결하는 두 마을의 번호이며, c는 도로를 지나는데 걸리는 시간입니다.

  - 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.

  - 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.

5. K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.

6. 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.

7. 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

 

입출력 예시

// case#1
N = 5
road = [[1,2,1], [2,3,3], [5,2,2], [1,4,2], [5,3,1], [5,4,2]]
K = 3
return = 4

// case#2
N = 6
road = [[1,2,1], [1,3,2], [2,3,2], [3,4,3], [3,5,2], [3,5,3], [5,6,1]]
K = 4
return = 4

---

In Details.

예시 1번

N = 5

road = [[1,2,1], [2,3,3], [5,2,2], [1,4,2], [5,3,1], [5,4,2]]

K = 3

 

Step1. current : 1, cost : 0

if문, else if문 조건에 만족하는 배열 road의 요소들만 로직을 체크하자

 

1) road = [1,2,1]

road = [1,2,1]
dist = [Infinity, 0, Infinity, Infinity, Infinity, Infinity];

current = 1;
currentCost = 0;

src = 1;
dest = 2;
cost = 1;

nextCost = currentCost + cost = 0 + 1 = 1;

// if문
src === current && nextCost < dist[dest] => 1 === 1 && 1 < Infinity => true

dist[dest] = dist[2] = 1;
heap.push({ node : 2, cost : 1});

=> dist = [Infinity, 0, 1, Infinity, Infinity, Infinity];

 

2) road = [1,4,2]

 

road = [1,4,2]
dist = [Infinity, 0, 1, Infinity, Infinity, Infinity];

current = 1;
currentCost = 0;

src = 1;
dest = 4;
cost = 2;

nextCost = currentCost + cost = 0 + 2 = 2;

// if문
src === current && nextCost < dist[dest] => 1 === 1 && 2 < Infinity => true

dist[dest] = dist[4] = 2;
heap.push({ node : 4, cost : 2});

=> dist = [Infinity, 0, 1, Infinity, 2, Infinity];

 

Step2. current : 2, cost : 1

 

1) road = [2,3,3]

road = [2,3,3]
dist = [Infinity, 0, 1, Infinity, 2, Infinity];

current = 2;
currentCost = 1;

src = 2;
dest = 3;
cost = 3;

nextCost = currentCost + cost = 1 + 3 = 4;

// if문
src === current && nextCost < dist[dest] => 2 === 2 && 4 < Infinity => true

dist[dest] = dist[3] = 4;
heap.push({ node : 3, cost : 4});

=> dist = [Infinity, 0, 1, 4, 2, Infinity];

 

2) road = [5,2,2]

road = [5,2,2]
dist = [Infinity, 0, 1, 4, 2, Infinity];

current = 2;
currentCost = 1;

src = 5;
dest = 2;
cost = 2;

nextCost = currentCost + cost = 1 + 2 = 3;

// else if문
dest === current && nextCost < dist[src] => 2 === 2 && 3 < Infinity => true

dist[src] = dist[5] = 3;
heap.push({ node : 5, cost : 3});

=> dist = [Infinity, 0, 1, 4, 2, 3];

 

Step3. current : 4, cost : 2

if문, else if문에 만족하는 경우가 없으므로 Skip!

road = [5,2,2]
dist = [Infinity, 0, 1, 4, 2, Infinity];

current = 2;
currentCost = 1;

src = 5;
dest = 2;
cost = 2;

nextCost = currentCost + cost = 1 + 2 = 3;

// else if문
dest === current && nextCost < dist[src] => 2 === 2 && 3 < Infinity => true

dist[src] = dist[5] = 3;
heap.push({ node : 5, cost : 3});

=> dist = [Infinity, 0, 1, 4, 2, 3];

 

Step4. current : 5, cost : 3

if문, else if문에 만족하는 경우가 없으므로 Skip!

 

Step5. current : 3, cost : 4

if문, else if문에 만족하는 경우가 없으므로 Skip!

 

 

Step6.

1번 정점에서 각 정점까지의 최소 거리 데이터를 담고 있는 dist를 return

return dist = [Infinity, 0, 1, 4, 2, 3];

 

Step7.

배열 dist 요소중 3보다 작거나 같은 요소는

0, 1, 2, 3

총 4개이므로 최종 반환 값은 4이다.

return 4;

---

My Answer. 

// 최소 힙
class MinHeap {
	constructor() {
    	this.heap = [null];
	}
    
    push(value) {
    	this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);
        
        while (parentIndex !== 0 && this.heap[parentIndex].cost > value.cost) {
        	this._swap(parentIndex, currentIndex)
            
            currentIndex = parentIndex;
            parentIndex = Math.floor(parentIndex / 2);
        }   
	}
    
    pop() {
    	if (this.isEmpty()) return;
        if (this.heap.length === 2) return this.heap.pop();
        
        const returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();
        
        let currentIndex = 1;
        let leftIndex = 2;
        let rightIndex = 3;
        
        while ((this.heap[leftIndex] && this.heap[currentIndex].cost > this.heap[leftIndex].cost) ||
        		(this.heap[rightIndex] && this.heap[currentIndex].cost > this.heap[rightIndex].cost)) {
        	if (this.heap[leftIndex] === undefined) {
            	this._swap(rightIndex, currentIndex)
            } else if (this.heap[rightIndex] === undefined) {
            	this._swap(leftIndex, currentIndex)
            } else if (this.heap[leftIndex].cost > this.heap[rightIndex].cost) {
            	this._swap(rightIndex, currentIndex)
            } else if (this.heap[leftIndex].cost <= this.heap[rightIndex].cost) {
            	this._swap(leftIndex, currentIndex)
            }
            leftIndex = currentIndex * 2;
            rightIndex = currentIndex * 2 + 1;
        }
    	return returnValue;
    }
 	
    isEmpty() {
    	return this.heap.length === 1;
    }
    
    _swap(a, b) {
    	[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
}

// 다익스트라 알고리즘 함수
function dijkstra(road, N) {
	const heap = new MinHeap();
    heap.push({ node : 1, cost : 0 }) // 1번 마을부터 시작
    
    const dist = [...Array(N + 1)].map(() => Infinity);
    dist[1] = 0;
    
    while (!heap.isEmpty()) {
    	const { node : current, cost : currentCost } = heap.pop();
        
        for (const [src, dest, cost] of road) {
        	const nextCost = cost + currentCost;
            
            if (src === current && nextCost < dist[dest]) {
            	dist[dest] = nextCost;
                heap.push({ node : dest, cost : nextCost });
            } else if (dest === current && nextCost < dist[src]) {
            	dist[src] = nextCost;
                heap.push({ node : src, cost : nextCost });
            }
        }
    }
    
    return dist;
}

function solution(N, road, K) {
	const dist = dijkstra(road, N);
    return dist.filter((el) => el <= K).length;
}

---

References.

• 코딩테스트 광탈 방지 A to Z : JavaScript (이선협)

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)