[해커랭크] Roads and Libraries [JAVA]

문제링크: www.hackerrank.com/challenges/torque-and-development/problem

Roads and Libraries | HackerRank

모든 노드들을 잇는 최소한의 간선 개수는 노드의 갯수 -1이다. 

그래서 도로를 고쳐서 도서관을 공유하는 비용을 최소한 하려면 도로를 N-1개만 고치면 된다. (MST 구성)

고장난 도로를 탐색해서 노드가 몇개인지 파악하기 위해 dfs 탐색을 했다.

또, N-1개의 도로의 수리비용보다 모든 노드에 도서관을 설치하는 비용이 적은 경우가 있어서 그중 작은 것을 정답으로 하면 된다.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
    
    public static boolean []visited;
    public static ArrayList<Integer> adj[];
    public static long dfs(int cur){
        long ret = 0;
        for(int i=0;i<adj[cur].size();i++){
            int next = adj[cur].get(i);
            if(visited[next]) continue;
            visited[next] = true;
            ret++;
            ret += dfs(next);
        }
        return ret;
    }
    // Complete the roadsAndLibraries function below.
    static long roadsAndLibraries(int n, int c_lib, int c_road, int[][] cities) {
        adj = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            adj[i] = new ArrayList<Integer>();
        }
        
        for(int i=0;i<cities.length;i++){
            int a= cities[i][0];
            int b = cities[i][1];
            adj[a].add(b);
            adj[b].add(a);
        }
        visited = new boolean[n+1];
        long cnt = 0;
        long ans = 0;
        for(int i=1;i<=n;i++){
            if(visited[i]) continue;
            visited[i] = true;
            cnt++;
            long roadCnt = dfs(i);
            ans += Math.min(c_road*roadCnt+c_lib,(roadCnt+1)*c_lib);
        }
        return ans;
    }
}