프로그래머스: 등산코스 정하기 - javascript (다익스트라 알고리즘 )

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

문제 풀이 힌트 

코드 설명 요약

1. 그래프 초기화:
   • 주어진 경로를 통해 각 노드의 인접 리스트를 생성합니다.
2. 최소 힙과 강도 배열 초기화:
   • MinHeap을 사용하여 각 게이트를 큐에 추가하고, 모든 지점에 대해 강도 값을 무한대로 설정합니다.
3. 다익스트라 알고리즘 변형:
   • 최소 힙을 사용하여 현재 노드에서 인접한 노드로의 경로 중 최대 강도가 가장 작은 경로를 탐색합니다.
   • 서밋에 도달하거나 이미 더 낮은 강도로 방문한 경우, 그 노드는 더 이상 탐색하지 않습니다.
4. 최소 강도 경로 선택:
   • 모든 서밋에 대해 최소 강도로 도달 가능한 서밋을 찾습니다.

문제 풀이 접근 방법

1. 그래프 구성:
   • 주어진 지점과 경로를 사용하여 그래프를 인접 리스트 형태로 구성합니다. 이는 각 지점에서 다른 지점으로의 연결과 고강도를 저장합니다.
2. 데이터 구조 초기화:
   • 최소 힙을 사용하여 경로의 최소 강도를 효율적으로 탐색할 수 있도록 합니다. 각 게이트를 힙에 추가하고, 초기 강도 값을 0으로 설정합니다.
3. 다익스트라 알고리즘 적용:
   • 게이트에서 시작하여 각 노드를 탐색하면서 강도 값을 업데이트합니다. 현재 노드에서 다음 노드로 이동할 때, 경로의 최대 강도를 최소화하는 방향으로 탐색을 진행합니다.
4. 최적 경로 찾기:
   • 모든 서밋을 탐색하여 최소 강도로 도달 가능한 서밋과 그 강도를 찾습니다. 결과적으로 최소 강도로 도달할 수 있는 서밋을 반환합니다.

이 접근 방식은 각 경로를 효율적으로 탐색하고, 최소 강도로 서밋에 도달할 수 있는 방법을 제공하여 주어진 문제를 해결합니다.

정답 풀이 코드 

class MinHeap {
    constructor() {
        // 힙을 저장할 배열 초기화
        this.heap = [];
    }

    // 힙의 크기를 반환하는 메소드
    size() {
        return this.heap.length;
    }

    // 힙이 비어있는지 확인하는 메소드
    isEmpty() {
        return this.size() === 0;
    }

    // 주어진 인덱스의 부모 노드 인덱스를 반환
    parentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    // 주어진 인덱스의 왼쪽 자식 노드 인덱스를 반환
    leftChildIndex(index) {
        return 2 * index + 1;
    }

    // 주어진 인덱스의 오른쪽 자식 노드 인덱스를 반환
    rightChildIndex(index) {
        return 2 * index + 2;
    }

    // 두 인덱스의 요소를 교환
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    // 힙에 요소를 추가하고, 위로 올리기(bubble up)를 통해 힙 성질 유지
    add(element) {
        this.heap.push(element);
        this.bubbleUp();
    }

    // 힙에서 최소값을 제거하고 반환, 아래로 내리기(bubble down)를 통해 힙 성질 유지
    poll() {
        if (this.isEmpty()) {
            return null; // 힙이 비어있으면 null 반환
        }
        if (this.size() === 1) {
            return this.heap.pop(); // 요소가 하나만 있을 경우, 바로 반환
        }
        const item = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return item;
    }

    // 추가된 요소를 적절한 위치로 이동하여 힙 성질 유지
    bubbleUp() {
        let index = this.size() - 1;
        while (index > 0 && this.heap[index][1] < this.heap[this.parentIndex(index)][1]) {
            this.swap(index, this.parentIndex(index));
            index = this.parentIndex(index);
        }
    }

    // 힙의 루트 요소를 적절한 위치로 내려 힙 성질 유지
    bubbleDown() {
        let index = 0;
        while (this.leftChildIndex(index) < this.size()) {
            let smallerChildIndex = this.leftChildIndex(index);
            if (this.rightChildIndex(index) < this.size() && this.heap[this.rightChildIndex(index)][1] < this.heap[smallerChildIndex][1]) {
                smallerChildIndex = this.rightChildIndex(index);
            }

            if (this.heap[index][1] <= this.heap[smallerChildIndex][1]) {
                break;
            }

            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
}

function solution(n, paths, gates, summits) {
    // 정상들을 쉽게 확인하기 위해 Set으로 변환
    const isSummit = new Set(summits);
    // 그래프를 인접 리스트로 구성
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b, c] of paths) {
        graph[a].push([b, c]);
        graph[b].push([a, c]);
    }

    // 최소 힙을 사용하여 처리할 노드 관리
    const queue = new MinHeap();
    // 각 노드까지의 최소 강도를 무한대로 초기화
    const intensity = Array(n + 1).fill(Infinity);

    // 각 출입구에서 시작하여 큐에 추가
    for (const gate of gates) {
        queue.add([gate, 0]);
        intensity[gate] = 0;
    }

    // 큐가 비어있지 않은 동안 루프
    while (queue.size()) {
        const [curNode, curWeight] = queue.poll();

        // 현재 노드가 정상이거나, 기록된 강도가 현재 강도보다 작으면 스킵
        if (isSummit.has(curNode) || intensity[curNode] < curWeight) continue;

        // 인접 노드 확인
        for (const [nextNode, nextWeight] of graph[curNode]) {
            const newWeight = Math.max(curWeight, nextWeight);
            if (newWeight < intensity[nextNode]) {
                intensity[nextNode] = newWeight;
                queue.add([nextNode, newWeight]);
            }
        }
    }

    // 결과를 찾기 위해 정상을 순회하며 최소 강도 확인
    let answer = [0, Infinity];
    summits.sort((a, b) => a - b);
    for (const summit of summits) {
        if (intensity[summit] < answer[1]) {
            answer = [summit, intensity[summit]];
        }
    }

    // 최적의 정상과 그 강도를 반환
    return answer;
}

Only 풀이 코드 

class MinHeap {
    constructor() {
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    parentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    leftChildIndex(index) {
        return 2 * index + 1;
    }

    rightChildIndex(index) {
        return 2 * index + 2;
    }

    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    add(element) {
        this.heap.push(element);
        this.bubbleUp();
    }

    poll() {
        if (this.isEmpty()) {
            return null;
        }
        if (this.size() === 1) {
            return this.heap.pop();
        }
        const item = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return item;
    }

    bubbleUp() {
        let index = this.size() - 1;
        while (index > 0 && this.heap[index][1] < this.heap[this.parentIndex(index)][1]) {
            this.swap(index, this.parentIndex(index));
            index = this.parentIndex(index);
        }
    }

    bubbleDown() {
        let index = 0;
        while (this.leftChildIndex(index) < this.size()) {
            let smallerChildIndex = this.leftChildIndex(index);
            if (this.rightChildIndex(index) < this.size() && this.heap[this.rightChildIndex(index)][1] < this.heap[smallerChildIndex][1]) {
                smallerChildIndex = this.rightChildIndex(index);
            }

            if (this.heap[index][1] <= this.heap[smallerChildIndex][1]) {
                break;
            }

            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
}

function solution(n, paths, gates, summits) {
    const isSummit = new Set(summits);
    const graph = Array.from({ length: n + 1 }, () => []);

    for (const [a, b, c] of paths) {
        graph[a].push([b, c]);
        graph[b].push([a, c]);
    }

    const queue = new MinHeap();
    const intensity = Array(n + 1).fill(Infinity);

    for (const gate of gates) {
        queue.add([gate, 0]);
        intensity[gate] = 0;
    }

    while (queue.size()) {
        const [curNode, curWeight] = queue.poll();

        if (isSummit.has(curNode) || intensity[curNode] < curWeight) continue;

        for (const [nextNode, nextWeight] of graph[curNode]) {
            const newWeight = Math.max(curWeight, nextWeight);
            if (newWeight < intensity[nextNode]) {
                intensity[nextNode] = newWeight;
                queue.add([nextNode, newWeight]);
            }
        }
    }

    let answer = [0, Infinity];
    summits.sort((a, b) => a - b);
    for (const summit of summits) {
        if (intensity[summit] < answer[1]) {
            answer = [summit, intensity[summit]];
        }
    }

    return answer;
}