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

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

 

문   제 : 

n개의 컴퓨터가 주어진다.

컴퓨터들은 0부터 n-1번의 번호를 가진다.

그리고 connections[i][j] 배열이 주어진다.

i번 컴퓨터와 j번 컴퓨터가 연결되었다는 정보를 가진 배열이다.

n과 connection[][] 배열이 주어졌을 때, 모든 컴퓨터들을 연결되게 하는 최소 횟수를 구해라.

만약 불가능 하다면, -1을 리턴해라.

 

 

Constraint

{ 1 <= n <= 10^5 }

{ 1 <= connections.length <= min(n * (n-1) / 2, 10^5) }

{ connections[i].length == 2 }

 

There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.

Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.

 

Example )

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

=======================================

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2

=======================================

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: There are not enough cables.

 

 

---

접   근 : 

HashSet을 이용한 노드관리, DFS를 이용해서 방문처리

---

해   결 : 

n개의 크기를 가진 visited배열을 선언한다. - n번 노드가 방문되었는지 안되었는지를 나타내는 배열이다.

HashSet을 원소로 가지는 List를 n개 선언한다. - n번 노드와 연결된 노드들을 자식으로 가지는 List이다.

 

List를 초기화 해준다.

 

방문이 안된 노드가 있으면 답을 +1 해준다.

dfs를 수행한다. - 모든 연결된 노드들이 방문처리된다.

 

답-1을 리턴한다. -> 처음에 +1을 해준상태로 시작했으므로 1을 빼준다.

 

dfs:

인자로 넘어온 i노드를 방문처리해준다.

그리고 i와 연결된 다른 노드들에게도 다시 재귀를 통해 방문처리를 해준다.

만약 이미 방문이 된 노드라면, 넘긴다.

---

결   과  :

class Solution {
    public int makeConnected(int n, int[][] connections) {
        
        if(connections.length+1 < n) return -1;

        ArrayList<Set<Integer>> node = new ArrayList<>();
        int[] visited = new int[n];
        int res=0;

        for(int i=0; i<n; i++){
            node.add(new HashSet<>());
        }

        for(int i=0; i<connections.length; i++){
            int start = connections[i][0];
            int end = connections[i][1];

            node.get(start).add(end);
            node.get(end).add(start);
        }

        for(int i=0; i<n; i++){
            if(visited[i] == 0) { // 방문 안됐으면
                res++;
                dfs(i, node, visited);
            }

        }
        return res-1;

    }
    public int dfs(int i, ArrayList<Set<Integer>> node, int[] visited){
        if(visited[i] != 0) return 0; // 방문이미 했다면 넘김
        visited[i] = 1; // 방문 처리
        for(int j: node.get(i)){ // i번째 노드에 대해 연결된 모든 노드들을 또 방문 처리
            dfs(j, node, visited);
        }
        return 1;
    }
}