[LeetCode] 1319번 Number of Operations to Make Network Connected 문제를 풀어보았다. (ft. java)

2023년 03월 23일 목요일 - 한화생명... 굉장하다..!

오늘 올려볼 문제는 1319번 Number of Operations to Make Network Connected 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

아니 이걸 한화가 이기네 ㄷㄷ

입력

사진에서도 볼 수 있듯이 int 값 1개와 2차원 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

n개의 컴퓨터와 컴퓨터끼리 연결되어있는 연결선들이 입력으로 들어온다.

모든 컴퓨터가 연결되도록 하게끔 연결선을 바꿔끼는 최소 횟수를 구하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

Union Find를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if(connections.length < n - 1) return -1;
        
        var sets = new boolean[n];
        var arr = setUnion(n, connections);
        int result = -1;
        
        for(var num : arr) {
            if(sets[num]) continue;
            
            result++;
            sets[num] = true;
        }
        
        return result;
    }
    
    private int[] setUnion(int n, int[][] connections) {
        int[] arr = new int[n];
        
        for(int i = 0; i < arr.length; i++) arr[i] = i;
        
        for(var connection : connections) {
            int a = findUnion(arr, connection[0]);
            int b = findUnion(arr, connection[1]);
            
            if(a < b) arr[b] = a;
            else arr[a] = b;
        }
        
        for(int i = 0; i < arr.length; i++) findUnion(arr, i);
        
        return arr;
    }
    
    private int findUnion(int[] arr, int n) {
        if(arr[n] == n) return n;
        
        return arr[n] = findUnion(arr, arr[n]);
    }
}

---

제출 화면

내일은 연차 룰루랄라~~

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.