Roads in HackerLand

사이트: HackerRank
난이도: 미디움
분류: Graph Theory

문제

무방향 그래프가 주어질 때, 각 정점 간의 최소 거리 값을 계산해서 이진수로 변환하라. 이 때 주어진 간선 정보는 [정점1, 정점2, 2의 지수] 값이 주어진다.

const [u, v, d] = [1, 3, 5];
// 즉 1번 정점에서 3번 정점간의 거리 값은 2의 5승(32)이 된다.

1. 나의 풀이

다익스트라 알고리즘으로 해결하려 했지만, 시간초과와 BigInt 계산이 잘 안되어서 일단 넘어가기로 했다.

// 일단은 시간이 오래 걸리긴 하지만 정답은 잘 반환한다.
class MeanHeap {
    constructor() {
        this.arr = [];
    }
    
    push(value) {
        this.arr.push(value);
        this.arr.sort((v1, v2) => v1.cost - v2.cost);
    }
    
    isEmpty() {
        return !this.arr.length;
    }
    
    pop() {
        if (this.isEmpty()) {
            return;
        }
        return this.arr.shift();
    }
}

function dijkstra(n, roads, start) {
    const heap = new MeanHeap();
    heap.push({ node: start, cost: 0 });
    
    const dist = Array.from(new Array(n + 1), () => Infinity);
    dist[start] = 0;

    while(!heap.isEmpty()) {
        const { node, cost } = heap.pop();
        
        for (const [src, dest, pow] of roads) {
            const nextCost = cost + Math.pow(2, pow);

            if (src == node && nextCost < dist[dest]) {
                dist[dest] = nextCost;
                heap.push({ node: dest, cost: nextCost });

            } else if (dest == node && nextCost < dist[src]) {
                dist[src] = nextCost;
                heap.push({ node: src, cost: nextCost });
            }
        }
    }
    
    return dist;
}

function roadsInHackerland(n, roads) {
    // Write your code here
    
    let result = 0;
    for (let i = 1; i < n; i++) {
        const dist = dijkstra(n, roads, i);

        for (let j = i + 1; j < n + 1; j++) {
            result += dist[j];
        }
    }
    
    return result.toString(2);
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.