[Java] leetcode 1319. Number of Operations to Make Network Connected

문제

https://leetcode.com/problems/number-of-operations-to-make-network-connected/description/

Number of Operations to Make Network Connected - LeetCode

최소 횟수를 구하는 문제 

풀이

풀이 알고리즘은 다음과 같다. 

1. dfs 탐색을 하여 네트워크 연결망 집합의 개수를 구한다.
2. 주어진 간선 <  ( 집합 원소의 수 -1 ) 이면 -1을 리턴
3. ( 집합 원소의 수 -1 ) 을 리턴한다.

이 문제는 어렵게 생각하면 어렵게 느껴지고, 쉽게 생각하면 쉽게 느껴졌다. 생각하기 나름. 

주어진 간선을 이동해서 모든 컴퓨터가 연결되게 하는 최소값을 리턴하는 문제이다.

 

 연결된 컴퓨터들을 하나의 원소로 생각하고 원소들의 집합을 생각해보면 , 각 캐이스마다 여러 집합들이 생긴다. 집합들의 원소 개수를 cardinality 라 한다.

 그러면 간선이 cardinality 보다 작은 캐이스를 제외하고  답은 cardinality -1 이다.  왜 그렇게 될까. 문제에서 요구한 것은 모든 컴퓨터들을 연결시키는 것이다. 하나의 네트워크 연결로 이루어진 집합은 다른 집합과 연결해야 한다. 연결되지 않은 집합의 개수를 cardinality로 구했으니깐 필요한 연결횟수는 ( cardinality-1 )이다. 문제에서 최솟값을 요구했음으로 그 값 그대로 리턴하면 된다. 

 

DFS 탐색은 재귀가 아닌 Queue로 구현했다.

Queue<Integer> Q = new LinkedList<>();
        boolean[] v = new boolean[n];
        for(int i =0 ;i < n; i++){
            if(!v[i]){
                v[i] = true;
                Q.offer(i);
                while(!Q.isEmpty()){
                    int curv = Q.poll();
                    for(int nv : g.get(curv)){
                        if(v[nv]) continue;
                        v[nv] = true;
                        Q.offer(nv);
                    }
                }
                cardinality++;
            }
        }

 

코드

자바

class Solution {
    ArrayList<ArrayList<Integer>> g ;
    public int makeConnected(int n, int[][] connections) {
        int len = connections.length;
        g = new ArrayList<>(); 
        if ( n-1 > len )return -1;
        for(int i = 0 ;i < n ;i++){
            g.add(new ArrayList<>());
        }
        for(int x[] : connections){
            g.get(x[0]).add(x[1]);
            g.get(x[1]).add(x[0]);
        }
        int cardinality =0 ;
        Queue<Integer> Q = new LinkedList<>();
        boolean[] v = new boolean[n];
        for(int i =0 ;i < n; i++){
            if(!v[i]){
                v[i] = true;
                Q.offer(i);
                while(!Q.isEmpty()){
                    int curv = Q.poll();
                    for(int nv : g.get(curv)){
                        if(v[nv]) continue;
                        v[nv] = true;
                        Q.offer(nv);
                    }
                }
                cardinality++;
            }
        }
        return cardinality-1;
    }
    
}