1939번 - 중량제한

1️⃣ 최대 힙(우선순위 큐), Greedy

 

✏️ 풀이 과정

섬과 다리라는 컨셉으로부터 그래프 관련 문제임을 유추할 수 있습니다. 문제에서 요구하는 사항은 조금 특이한데 최단 거리나 최장 거리가 아니라 시작점에서 끝점으로 가는 최장 경로(원래 거리가 아니라 무게인데 편의상 거리처럼 표현하겠습니다.)에서 가중치의 최솟값을 구해야 합니다.(사실 저 최솟값을 가장 크게 만드는 경로가 최장 경로라는 걸 알았다면 문제가 해결된 것이나 마찬가지입니다.)

 

이를 구현할 수 있는 방법은 굉장히 많은데 Greedy, Pruning, Kruskal, Dijkstra, Dynamic Programing, 이분탐색 등의 방법으로 문제를 해결할 수 있습니다. 여기서는 최대 힙(우선순위 큐)를 통해 Greedy Algorithm으로 항상 더 큰 가중치를 선택하다가 목표점에 도달하면 종료하는 방법으로 가장 높은 가중치들만 갖는 경로를 구현합니다.

 

구현은 BFS와 비슷한 방법으로 하지만 최대 힙을 이용하기 때문에 결과적으로 다익스트라 알고리즘과 비슷해집니다. 종착점에 도착했을 때 종료하기 때문에 더 빠르게 끝낼 수 있습니다. while문 안에서는 현재 가중치가 지금까지 나온 최솟값보다 작으면 업데이트하고 종착점에 도착하면 break, 이외의 경우에는 연결된 정점들을 모두 최대 힙에 넣습니다.

 

break 이후 현재까지 업데이트된 최솟값을 출력하면 문제가 해결됩니다.

 

⏱ 시간 복잡도

while문에서 break가 일어나지 않으면 모든 간선을 힙에 넣기 때문에 O(ElogV)가 됩니다.(힙에 add나 remove를 할 때 O(logV)이므로

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const swap = (arr, a, b) => {
    const tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
};

class MaxHeap {
    constructor() {
        this.heap = [];
        this.cnt = 0;
    }

    isEmpty() {
        if (this.cnt === 0) {
            return true;
        } else {
            return false;
        }
    }

    add(item) {
        this.heap[++this.cnt] = item;
        let idx = this.cnt;
        while (idx > 1) {
            if (this.heap[parseInt(idx / 2)].w < this.heap[idx].w) {
                swap(this.heap, parseInt(idx / 2), idx);
                idx = parseInt(idx / 2);
            } else {
                break;
            }
        }
    }

    remove() {
        if (this.cnt === 0) {
            return 0;
        }
        const res = this.heap[1];
        this.heap[1] = this.heap[this.cnt--];
        let idx = 1;
        while (2 * idx <= this.cnt) {
            if (2 * idx == this.cnt) {
                if (this.heap[2 * idx].w > this.heap[idx].w)
                    swap(this.heap, idx, 2 * idx);
                break;
            } else {
                if (this.heap[2 * idx + 1].w > this.heap[2 * idx].w) {
                    if (this.heap[2 * idx + 1].w > this.heap[idx].w) {
                        swap(this.heap, idx, 2 * idx + 1);
                        idx = 2 * idx + 1;
                    } else {
                        break;
                    }
                } else {
                    if (this.heap[2 * idx].w > this.heap[idx].w) {
                        swap(this.heap, idx, 2 * idx);
                        idx = 2 * idx;
                    } else {
                        break;
                    }
                }
            }
        }
        return res;
    }
}

class Node {
    constructor(v, w, link) {
        this.v = v;
        this.w = w;
        this.link = link;
    }
}

const [N, M] = input[0].split(" ").map(Number);
const adjList = [];
let from, to, w;

for (let i = 1; i <= M; i++) {
    [from, to, w] = input[i].split(" ").map(Number);
    adjList[from] = new Node(to, w, adjList[from]);
    adjList[to] = new Node(from, w, adjList[to]);
}
const hp = new MaxHeap();
const INF = 1000000001;
let min = INF;
const [start, end] = input[M + 1].split(" ").map(Number);
hp.add(new Node(start, INF, null));
let cur;
visited = [];
visited[start] = true;
while (!hp.isEmpty()) {
    cur = hp.remove();
    visited[cur.v] = true;
    if (cur.w < min) {
        min = cur.w;
    }
    if (cur.v === end) {
        break;
    }
    for (let n = adjList[cur.v]; n != null; n = n.link) {
        if (!visited[n.v]) {
            hp.add(n);
        }
    }
}

console.log(min);