도서관 건설 비용 <= 도로 연결 비용인 경우
도로 연결 비용보다 도서관 건설 비용이 저렴한 경우에는 각 도시별로 도서관을 짓는게 최소 비용
도서관 건설 비용 > 도로 연결 비용인 경우
특정 한 도시에 도서관을 짓고, 연결할 수 있는 모든 도시의 도로를 연결
1개의 도로로 2개의 도시를 연결 할 수 있으므로, 2개의 도시를 연결한 경우 1개의 도로 건설 비용만 부가
자료구조
구현 코드에서는 모든 연결된 도시의 경우의 수를 파악하기 위해 그래프 사용
// 도서관 건설 최소 비용을 구함
static long roadsAndLibraries(int n, int c_lib, int c_road, int[][] cities) {
List<ArrayList<Integer>> roadGraph = initRoadGraph(n, cities);
boolean[] visited = new boolean[n];
long totalCost = 0;
for (int i = 0; i < roadGraph.size(); i++) {
if (!visited[i]) {
if (c_lib > c_road) {
totalCost += c_lib + (c_road * (countNumberOfVisitsByDfs(i, visited, roadGraph) - 1));
} else {
totalCost += c_lib * countNumberOfVisitsByDfs(i, visited, roadGraph);
}
}
}
return totalCost;
}
// 도시간 연결하는 그래프
static List<ArrayList<Integer>> initRoadGraph(int n, int[][] cities) {
List<ArrayList<Integer>> roadGraph = new ArrayList<>();
for (int i = 0; i < n; i++) {
roadGraph.add(new ArrayList<>());
}
for (int i = 0; i < cities.length; i++) {
roadGraph.get(cities[i][0] - 1).add(cities[i][1] - 1);
roadGraph.get(cities[i][1] - 1).add(cities[i][0] - 1);
}
return roadGraph;
}
// 도시별 방문 횟수
static long countNumberOfVisitsByDfs(int index, boolean[] visited, List<ArrayList<Integer>> roadGraph) {
long cityVisitCount = 1;
visited[index] = true;
for (int i = 0; i < roadGraph.get(index).size(); i++) {
if (!visited[roadGraph.get(index).get(i)]) {
cityVisitCount += countNumberOfVisitsByDfs(roadGraph.get(index).get(i), visited, roadGraph);
}
}
return cityVisitCount;
}