Daily LeetCode Challenge - 1319. Number of Operations to Make Network Connected

Problem From.

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

오늘 문제는 각 컴퓨터가 연결되어있는 상태를 보여주는 connections 배열과 총 선의 수 n 이 주어졌을때, 모든 컴퓨터를 연결시키기 위해 선을 바꾸어 주어야하는 갯수를 반환해야하는 문제였다.

오늘 문제도 역시 union find 알고리즘을 통해서 풀 수 있었는데,
먼저 제일 처음 0번째 컴퓨터부터 시작해서 각 컴퓨터로 나아갈때, 경로를 압축시켜서 각 경로마다 다른 컴퓨터와 연결되어있지 않고 따로 떨어져 있는 컴퓨터의 갯수를 배열에 저장해둔다.
find 를 통해 각 배열에 연결되어있는 컴퓨터를 저장한뒤, 마지막에 parents 배열을 돌며 따로 떨어져 있는 컴퓨터의 수를 반환하면 된다.

class Solution {
    
    private lateinit var parents: IntArray

    fun makeConnected(n: Int, connections: Array<IntArray>): Int {
        if (connections.size < (n - 1)) return -1
        
        var answer = 0
        
        parents = IntArray(n + 1) { it }
        
        for ((a, b) in connections) {
            val px = find(a)
            val py = find(b)
            parents[py] = px
        }
        
        for(i in 0 until n) {
            if (find(i) == i) answer++
        }
        return answer - 1
    }
    
    private fun find(x: Int): Int {
        if (parents[x] != x) parents[x] = find(parents[x])
        return parents[x]
    }
}