사이트: HackerRank
난이도: 미디움
분류: Graph Theory
시민들이 도서관을 이용할 수 있기 위해 각 마을에 도서관을 지으려고 한다. 연결된 도로가 있다면 시민들은 옆 마을로 이동하여 도서관을 이용할 수 있다. 아직 각 마을들은 도서관이 지어지지 않았고, 길도 연결되지 않았다. 각 마을들을 연결할 수 있는 지도 정보가 주어질 때 도서관 건설비용과 도로 개설비용이 가장 적게 드는 값을 반환하라.
해당 문제는 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);
}
바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.