Roads and Libraries

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

문제

시민들이 도서관을 이용할 수 있기 위해 각 마을에 도서관을 지으려고 한다. 연결된 도로가 있다면 시민들은 옆 마을로 이동하여 도서관을 이용할 수 있다. 아직 각 마을들은 도서관이 지어지지 않았고, 길도 연결되지 않았다. 각 마을들을 연결할 수 있는 지도 정보가 주어질 때 도서관 건설비용과 도로 개설비용이 가장 적게 드는 값을 반환하라.

1. 나의 풀이

해당 문제는 graph의 연결요소(connected component)를 찾고 해당 컴포넌트의 노드 수를 계산하여 도로+도서관 건설비용이 큰지 도서관만 건설하는비용이 큰지 비교하여 반환하면 되는 문제이다.
그래프 문제는 이제 적응이 된건지 생각보다 쉽게 해결할 수 있었다.

function dfs(graph, start, visited) {
    const stack = [start];
    let count = 1;
    
    visited[start] = true;
    
    while(stack.length) {
        const current = stack.pop();
        
        for (const next of graph[current]) {
            if (!visited[next]) {
                count++;
                stack.push(next);
                visited[next] = true;
            }
        }
    }
    
    return count;
}

function roadsAndLibraries(n, c_lib, c_road, cities) {
    // Write your code here
    const graph = Array.from(new Array(n + 1), () => []);
    
    cities.forEach(([c1, c2]) => {
        graph[c1].push(c2);
        graph[c2].push(c1);
    });
    
    const visited = [];
    const components = [];

    for (let i = 1; i <= n; i++) {
        if (!visited[i]) {
            components.push(
                dfs(graph, i, visited)  
            );
        }
    }

    let onlyLib = 0, libWithRoad = 0;
    
    components.forEach(component => {
        onlyLib += (c_lib * component);
        libWithRoad += c_lib + ((component - 1) * c_road);
    });
    
    return Math.min(onlyLib, libWithRoad);
}

2. 다른사람의 풀이

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