[Data Structure / Algorithms] Disjoint-Set Structure (Union - Find Algorithms)

주제: 서로소 집합 찾아내기

---

서로소란 집합(Disjoint Sets)이란

• 서로소 집합이란 공통 원소가 없는 두 집합을 의미합니다.
• 예를 들어 집합 {1, 2}와 집합 {3, 4}는 서로소 관계입니다. 반면에 집합 {1, 2}와 집합 {2,3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아닙니다.
• 트리 구조를 활용한 Disjoint Set 즉, Union-FInd 자료구조는 각 원소를 트리의 노드로 포현하며, 각 트리는 하나의 집합을 나타냅니다.
• 이 구조에서는 각 노드가 자신의 부모 노드를 가리키는 방식으로 연결됩니다. 트리의 루트 노드는 해당 집합의 대표자 역할을 담당합니다.

동작방식

1. 초기화
   • 각 원소는 자신만을 포함하는 고유한 집합에 속합니다. 이를 표현하기 위해 각 원소는 자신을 가리키는 포인터(parent 배열)을 갖습니다.
2. Find
   • 특정 원소가 어느 집합에 속하는지를 확인합니다. 이는 원소가 가리키는 포인터를 따라가 최상위 원소를 찾는 과정을 통해 이루어집니다. 최상위 원소는 집합의 대표자로 간주합니다.
3. Union
   • 두 집합을 하나로 합칩니다. 일반적으로 한 집합의 루트 원소가 다른 집합의 루트 원소를 가리키도록 설정하여 두 집합을 합칩니다.

효율성

• 시간 복잡도

  • Find: 최악의 경우 $O(N)$ 이지만 경로 압축(Path Compression)을 사용하면 거의 $O(1)$에 가깝게 동작합니다.
  • Union: $O(1)$의 시간 복잡도를 나타내고있습니다. 두 트리의 루트를 찾고 하나를 다른 하나에 연결하는 간단한 작업이므로 매우 빠릅니다.

• 공간 복잡도

  • $O(N)의 공간 복잡도를 나타냅니다. 여기서 N은 원소의 개수입니다.

한계

• 초기 구현에서 Find 연산은 트리가 깊어질수록 비효율적일 수 있습니다. 이를 해결하기 위해 경로 압축 또는 Union by Rank와 같은 최적화 기법을 사용할 수 있습니다.
• Disjoint Set 자료구조는 특히 연결 요소가 동적으로 변하지 않는 상황에서 효과적입니다. 자주 변하는 경우에는 추가 작업이 필요할 수 있습니다.

활용

• 연결 요소, 최소 신장 트리(MST)를 찾는 크루스칼 알고리즘 등에 사용됩니다.
• 서로 연결된 픽셀의 집합을 찾는 데 사용될 수 있습니다.
• 네트워크 시스템에서 연결된 컴포넌트를 파악하는 데 사용됩니다.

구현

최적화 기법

Path Compression

• Find 연산 시, 찾은 루트 노드를 각 노드의 부모로 직접 설정하여, 트리의 높이를 줄입니다. 이를 통해 다음 Find 연산의 속도를 높입니다.
• 즉, Find 연산을 수행하면서 거쳐가는 모든 노드들의 부모를 해당 집합의 루트 노드로 직접 연결함으로써, 다음 Find 연산의 효율성을 크게 향상 시킵니다.
• 경로 압축을 사용하면 Find 연산의 평균 시간 복잡도가 거의 $O(1)$에 가깝게 됩니다. 이는 각 Find 연산 후에 트리 구조가 점점 더 플릿해지기 때문입니다.
• 결국 이후 Find 연산은 대부분 루트 노드에 매운 가까운 위치에서 시작되므로 매우 빠르게 처리됩니다.

Union by Rank

• 두 트리를 합칠 때, 높이(랭크)가 낮은 트리를 높은 트리의 하위에 추가합니다. 이는 트리의 높이가 불필요하게 커지는 것을 방지합니다.

Disjoint Set 구현

struct DisjointSet { 
	var parent: [Int]
	var rank: [Int]
	
	init(count: Int) { 
		// 자기 자신이 부모가 될 수 있도록 초기화 합니다.
		parent = Array(0..<count)
		// rank를 모두 0으로 초기화 합니다. 
		rank = Array(repeating: 0, count: count)
	}
	
	mutating func find(_ x: Int) -> Int { 
		if parent[x] != x { 
			// 경로 압축 (둘 다 가능)
			parent[x] = find(parent[x]) 
			// parent[x] = find(parent[parent[x]])
		}
		return parent[x]
	}
	
	// Rank가 높은 노드가 부모가 됩니다. 
	mutating func unionByRank(_ x: Int, _ y: Int) { 
		let xRoot = find(x)
		let yRoot = find(y)
		
		// 각 부모가 다를때 실행 
		if xRoot != yRoot { 
			// 랭크가 낮은 집합을 합칩니다. 즉, 랭크가 높은 값이 루트가 됩니다. 
			if rank[xRoot] < rank[yRoot] { 
				parent[xRoot] = yRoot
			} else if rank[xRoot] > rank[yRoot] { 
				parent[yRoot] = xRoot
			// 랭크가 같을 경우, 한 쪽을 다른 쪽의 부모로 만들고 해당 부모의 랭크를 1 증가시킵니다. 
			} else { 
				parent[yRoot] = xRoot
				rank[xRoot] += 1
			}
		}
	}
	
	// 집합안에서 가장 낮은 숫자가 부모가 됩니다.
	mutating func unionByAscending(_ x: Int, _ y:Int) { 
		let xRoot = find(x)
		let yRoot = find(y)
		
		if xRoot != yRoot { 
			if rank[xRoot] < rank[yRoot] { 
				parent[xRoot] = yRoot
			} else if rank[xRoot] > rank[yRoot] { 
				parent[yRoot] = xRoot
			// 두 랭크가 같을 때 숫자가 낮은 노드를 부모로 설정합니다. 
			} else { 
				if xRoot < yRoot { 
					parent[yRoot] = xRoot
					rank[xRoot] += 1
				} else { 
					parent[xRoot] = yRoot
					rank[yRoot] += 1
				}
			}
		}
	}
}

let n = 6

var disjointSet = DisjointSet(count: n + 1)

let edges = [(1,4), (2,3), (2,4), (5,6)]

for edge in edges {
    disjointSet.unionByAscending(edge.0, edge.1)
}

var groups: [Int: [Int]] = [:]

for i in 1...n {
    let root = disjointSet.find(i)
    groups[root, default: []].append(i)
}


print(groups)

print(disjointSet.parent)
print(disjointSet.rank)

[5: [5, 6], 1: [1, 2, 3, 4]]
[0, 1, 1, 1, 1, 5, 5]
[0, 2, 1, 0, 0, 1, 0]

예제 1 집합의 표현 (백준 골드5)

문제

• 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
• 집합을 표현하는 프로그램을 작성하시오.

입력

• 첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 $1$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

• 1로 시작하는 입력에 대해서 $a$와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제한

•  $1 ≤ n ≤ 1\,000\,000$ 
•  $1 ≤ m ≤ 100\,000$ 
•  $0 ≤ a, b ≤ n$ 
•  $a$, $b$는 정수
•  $a$와 $b$는 같을 수도 있다.

예제 입력 1 

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1 

NO
NO
YES

풀이

• 초기 n+1 집합이므로 parent의 count를 0...count까지 맞춰준다음, 주어지는 값에 따라 union과 find 메서드를 적절히 활용해주면 된다.
• 여기서 String값을 출력해주는데 오타를 조심하자.

import Foundation

struct DisjointSet {
    var parent: [Int]
    var rank: [Int]
    
    init(count: Int) {
        // n+1 까지 집합을 만들기 위해
        parent = Array(0...count)
        rank = Array(repeating: 0, count: count + 1)
    }
    
    mutating func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        
        return parent[x]
    }
    
    mutating func union(_ x: Int, _ y: Int) {
        let xRoot = find(x)
        let yRoot = find(y)
        
        if xRoot != yRoot {
            if rank[xRoot] < rank[yRoot] {
                parent[xRoot] = yRoot
            } else if rank[xRoot] > rank[yRoot] {
                parent[yRoot] = xRoot
            } else {
                parent[yRoot] = xRoot
                rank[xRoot] += 1
            }
        }
    }
}

let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }

let n = testCase[0]
let m = testCase[1]

var disjointSet = DisjointSet(count: n)

for _ in 0..<m {
    let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }
    
    let check = testCase[0]
    let a = testCase[1]
    let b = testCase[2]
    
    if check == 0 {
        disjointSet.union(a, b)
    } else {
        let x = disjointSet.find(a)
        let y = disjointSet.find(b)
		
		// 이 부분에서 오타 발생으로 두번 틀림
        if x == y {
            print("YES")
        } else {
            print("NO")
        }
    }
}

예제 2 여행 가자 (백준 골드4)

문제

• 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
• 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력

• 첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

예제 입력 1 

3
3
0 1 0
1 0 1
0 1 0
1 2 3

예제 출력 1 

YES

풀이

• 그래프로 입력받아서 해당 그래프의 값에 대해 서로소 집합을 구하면 된다.

import Foundation

struct DisjointSet {
    var parent: [Int]
    var rank: [Int]
    
    init(count: Int) {
        parent = Array(0..<count)
        rank = Array(repeating: 0, count: count)
    }
    
    mutating func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        
        return parent[x]
    }
    
    mutating func union(_ x: Int, _ y: Int) {
        let xRoot = find(x)
        let yRoot = find(y)
        
        if xRoot != yRoot {
            if rank[xRoot] < rank[yRoot] {
                parent[xRoot] = yRoot
            } else if rank[xRoot] > rank[yRoot] {
                parent[yRoot] = xRoot
            } else {
                parent[yRoot] = xRoot
                rank[xRoot] += 1
            }
        }
    }
}

// 도시의 수
let n = Int(readLine()!)!
// 여행갈 도시의 수
let m = Int(readLine()!)!

var disjointSet = DisjointSet(count: n)


for i in 0..<n {
    let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }
    
    for j in 0..<n {
	    // 해당 부분에서 testCase[j] == 1가 아닌 j == 1로 해서 틀렸음
        if testCase[j] == 1 {
            disjointSet.union(i, j)
        }
    }
}

// 주어진 값에 대해 -1 하는 부분을 입력과 동시에 map으로 처리 
let travel = readLine()!.components(separatedBy: " ").map { Int($0)! - 1 }

let first = disjointSet.find(travel[0])

// 최초 값을 "YES"로 하며 travel 값에 대해 for문을 돌고, first와 다르다면 NO로 변경 후 break
var result = "YES"

for city in travel {
    if disjointSet.find(city) != first {
        result = "NO"
        break
    }
}

print(result)

호텔 방 배정 (프로그래머스 카카오 인턴십 19, Lv4)

문제

• [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
• "스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
• 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
  고객은 투숙하기 원하는 방 번호를 제출합니다.
  고객이 원하는 방이 비어 있다면 즉시 배정합니다.
  고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
• 예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호	배정된 방 번호
1	1
3	3
4	4
1	2
3	5
1	6

• 전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• k는 1 이상 1012 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
• 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

[입출력 예]

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

풀이

• 기존 부모 배열을 Int64처리를 위해 해쉬값을 하는 Dictionary로 처리합니다. 이때 dictionary에서 해당 key값의 유무로 parent를 판별합니다.
• 문제의 조건에 맞춰서 부모값을 저장하는것이 아니라 부모 값에 +1 된 값을 저장해서 다음 동일 값이 들어오면 +1 된 값을 부여하는 형식으로 Union-Find를 활용할 수 있습니다.

import Foundation

struct DisjointSet {
    var parent: [Int64: Int64]

    init() {
        parent = [Int64: Int64]()
    }

    mutating func find(_ num: Int64) -> Int64 {
        if let p = parent[num], p != num {
            parent[num] = find(p)
            return parent[num]!
        } else {
            parent[num] = num
            return num
        }
    }
    
    mutating func union(_ num: Int64) -> Int64 {
        let root = find(num)
        
        parent[root] = root + 1
        return root
    }
}

func solution(_ k: Int64, _ room_number: [Int64]) -> [Int64] {
    var disjointSet = DisjointSet()
    var result: [Int64] = []

    for room in room_number {
        let nextRoom = disjointSet.union(room)
        
        result.append(nextRoom)
    }

    return result
}


solution(10, [1,3,4,1,3,1])

출처(참고문헌)

• 이것이 코딩 테스트이다 - 나동빈
• https://victorqi.gitbooks.io/swift-algorithm/content/union-find.html?q=
• https://www.acmicpc.net/problem/1717
• https://www.acmicpc.net/problem/1976
• https://school.programmers.co.kr/learn/courses/30/lessons/64063

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.