Swift ) LeetCode(Medium) - Friend Circles (Union-Find)

leetcode.com/problems/friend-circles/

Friend Circles - LeetCode

안녕하세요 후르륵짭짭 입니다.

오늘은 유니온 파인드 알고리즘을 들고 왔습니다.

유니온 파인드는 서로 같은 집합인지 알려주는 알고리즘인데,

사실 잘 몰라서 열심히 찾아봤습니다 ㅎㅎㅎ

그럼 바로 설명을 해보도록 하겠습니다.

 

** 유니온 파인드란 **

위에서 설명한 것 처럼, 유니온 파인드는 요소가 서로 같은 집합인지 알려주면서

서로 같은 집합으로 병합 시켜주기도 합니다.

그럼 코드로 하나씩 알아보도록 하겠습니다.

처음에는 이렇게 5개의 노드가 있다면 서로 연결 되어 있지 않음을 표현하기 위해 배열에 자기를 넣어줍니다.

var nodes : [Int]
    
init(_ N : Int) {
   nodes = Array(0..<N)
 }

그리고 아래 처럼 연결 시켜줍니다.

mutating func unionElement(_ a : Int , _ b : Int){
        
        let rootOf_A = findParent(a)
        let rootOf_B = findParent(b)
        
        if rootOf_A < rootOf_B{
            nodes[rootOf_B] = rootOf_A
        }
        else{
            nodes[rootOf_A] = rootOf_B
        }
        
    }

그러면 서로의 부모를 찾고 부모가 더 작은 값을 큰 쪽에 넣어줍니다 .

0의 자식으로 1이 들어가게 됩니다. 그러면서 1의 위치에 자기의 부모를 값으로 넣어줍니다.

그래서 1의 루트를 탐색을 할 때, 재귀를 사용해서 0번째 노드로 찾아가는 겁니다.

하지만!!! 이런 방식은 아래 처럼 점점 트리의 높이가 길어지게 할 수 있습니다.

따라서 3번에서 부모 노드를 탐색할 때 시간이 길어지게 됩니다. 만약 3이 아니라 높이가 10억이면,,,, 시간이 너무 길어집니다.

그래서 이 방식을 해결하기 위해 최상단 노드를 찾으면 바로 루트 노드를 넣어주는 겁니다.

mutating func findParent(_ a : Int) -> Int{
        
        if nodes[a] == a {
            return a
        }
        
        nodes[a] = findParent(nodes[a])
        
        return nodes[a]
    }

 

위의 코드 처럼 하면, 노드를 찾기를 했을 때, 위에 그림 처럼 만들어 줍니다. 

하지만, 찾기를 안 했을 때는 잘못된 노드를 가르치게 됩니다.

위의 그림을 본다면 0과 2를 연결 시켰는데, 2의 하부 요소 3,4는 0이 안되고 2만 0이 된 것을 확인 할 수 있습니다.

따라서 마지막에 모든 노드에 대해서 부모 노드가 어떻게 되는지 탐색을 해줘야합니다.

for xindex in 0..<M.count{
                   
    findParent(xindex)
                   
}

 

하지만 끝이 아닙니다,,,, ㅠㅠ 

하나 더 추가 할게 있습니다. 바로 트리 높이 작업 입니다.

만약 위 그림 처럼 단순히 더 작은 루트 노드 쪽으로 Union 작업을 해준다면,

마지막 처럼 트리 높이가 더 높아진 것을 알 수 있습니다. 

그래서 트리의 높이가 더 높은 쪽의 값을 높이가 더 작은 쪽으로 넣어줘야 높이가 높아지지 않게 할 수 있습니다.

 

이렇게 유니온 파인드에 대한 기초적인 개념이 다 끝났습니다!!!

아래는 최종 코드 입니다.

struct DisJointSet2{
    
    var nodes : [Int]
    var height : [Int]
    
    init(_ N : Int) {
        nodes = Array(0..<N)
        height = Array(repeating: 1, count: N)
    }
    
    mutating func findParent(_ a : Int) -> Int{
        
        if nodes[a] == a {
            return a
        }
        
        nodes[a] = findParent(nodes[a])
        
        return nodes[a]
    }
    
    mutating func unionElement(_ a : Int , _ b : Int){
        
        let rootOf_A = findParent(a)
        let rootOf_B = findParent(b)
        
        if rootOf_A == rootOf_B {return}
        
        if height[rootOf_A] < height[rootOf_B]{
            nodes[rootOf_A] = rootOf_B
        }
        else if height[rootOf_A] > height[rootOf_B]{
            nodes[rootOf_B] = rootOf_A
        }
        else{
        
        if rootOf_A < rootOf_B{
            nodes[rootOf_B] = rootOf_A
            height[rootOf_A] += 1
        }
        else{
            nodes[rootOf_A] = rootOf_B
            height[rootOf_B] += 1
        }
            
        }
        
    }

}

 

** 문제 내용 **

단순히 사이클을 구하는 문제입니다. 

만약에 1과 2와 3이 친구 이고 4와 5가 친구가 아니라면 친구의 그룹은 총 2개가 됩니다.

transitive - 이행성 : A와 B가 친구이고 B와 C가 친구라면 A와 C도 친구이다.

 

** 해설 **

- 최종 코드 -

struct DisJointSet{
    
    var nodes : [Int]
    var height : [Int]
    
    init(_ N : Int) {
        nodes = Array(0..<N)
        height = Array(repeating: 1, count: N)
    }
    
    mutating func findParent(_ a : Int) -> Int{
        
        if nodes[a] == a {
            return a
        }
        
        nodes[a] = findParent(nodes[a])
        
        return nodes[a]
    }
    
    mutating func unionElement(_ a : Int , _ b : Int){
        
        let rootOf_A = findParent(a)
        let rootOf_B = findParent(b)
        
        if rootOf_A == rootOf_B {return}
        
        if height[rootOf_A] < height[rootOf_B]{
            nodes[rootOf_A] = rootOf_B
        }
        else if height[rootOf_A] > height[rootOf_B]{
            nodes[rootOf_B] = rootOf_A
        }
        else{
        
        if rootOf_A < rootOf_B{
            nodes[rootOf_B] = rootOf_A
            height[rootOf_A] += 1
        }
        else{
            nodes[rootOf_A] = rootOf_B
            height[rootOf_B] += 1
        }
            
        }
        
    }

}


class Solution {
    func findCircleNum(_ M: [[Int]]) -> Int {
            
        var relation = DisJointSet.init(M.count)
        
        for (yindex , yelement) in M.enumerated(){
            
            for (xindex, xelement) in yelement.enumerated(){
                
                if xelement == 1 {
                    
                    relation.unionElement(yindex, xindex)
                    
                }
                
            }
            
        }
        
        for xindex in 0..<M.count{
                   
            relation.findParent(xindex)
                   
        }
        
        return Set(relation.nodes).count
    }
}

이 문제는 DFS랑 BFS등 여러가지 방법으로 풀 수 있는데, 저는 Union-Find를 공부하기 위해서 

유니온 파인드로 풀었습니다.

지금 까지 유니온 파인드를 적용한 것을 바로 사용하면 쉽게 풀 수 있는데,,, 저는 처음에 많이 헷갈렸습니다.

func unionParent(_ list : inout [Int], _ personOne : Int, _ personTwo : Int){
        
        let one = findParent(&list, personOne)
        let two = findParent(&list, personTwo)
        
        if one < two {
            list[personTwo] = one
        }
        else if two < one {
            list[personOne] = two
        }
        
    }

이렇게 입력으로 주어진 노드에 루트 노드를 넣어주는 방식을 했기 때문에 큰 문제가 발생 했습니다....

그래서 결국 3중 포문을 해서 해결 했고,, 유니온 파인드에 대해 더욱 심도 있게 공부 했었습니다.

 

참고 사이트 : 

ssungkang.tistory.com/entry/Algorithm-유니온-파인드Union-Find

[Algorithm] 유니온 파인드(Union - Find)