유니온 파인드(Union-Find)

안녕하세요. 밀쿄입니다.

오늘은 유니온 파인드라는 알고리즘에 대해서 알아보겠습니다.

 

유니온 파인드는 그래프 알고리즘의 일종 입니다.

그리고 합집합 찾기라는 의미를 담고 있습니다.

이렇게 말하면 감이 안오지만 쉽게 말하자면

"여러 가지 노드가 있을 때, 두 노드를 선택하여

가 같은 그래프에 속하는 지 판별하는 알고리즘"

이라고 생각하시면 편할 것 같습니다.

 

따라서 이 알고리즘은 두 가지 연산으로 이루어져있습니다.

이름에도 나와있듯이 유니온(Union) 연산과 찾는(Find) 연산입니다.

Union은 두 노드가 속해있는 집합을 합치는 연산입니다.

Find는 한 노드가 어떤 집합에 포함되어 있는 지 찾는 연산 입니다.

 

예시를 하나 들어보겠습니다.

처음에는 1, 2, 3이 있다고 가정해봅시다.

각각의 원소들은 연결된 정보가 없기 때문에 부모를 자기 자신으로 가지고 있습니다.

1-1 . 2-2, 3-3 이런식으로 말이죠.

만약 여기서 1-2하고 연결되어있고 2-3이 연결되어있다고 입력이 들어온다고 가정해봅시다.

1과 2는 서로 부모 노드가 다르므로 재귀 함수를 통해서 연결 여부를 파악하게 됩니다 (find 연산)

재귀 함수 결과 1과 2는 서로 다른 부모를 가졌으므로 연결 해줍니다. (union 연산)

2하고 3을 연결할때는 2의 부모와 3의 부모를 찾습니다. (find 연산)

부모를 찾아보니 2의 부모는 1이고 3의 부모는 3인것을 찾습니다.

따라서 두 부모가 다르므로 1과 3을 연결해줍니다 (union 연산)

결국 연산결과 부모가 모두 1이기 때문에 세 노드는 모두 같은 그래프에 속한다는 것을 알 수 있습니다.

이것이 유니온 파인드 알고리즘 입니다.

 

대표적인 문제를 하나 풀어보겠습니다.

www.acmicpc.net/problem/2606

2606번: 바이러스

먼저 처음에는 연결정보가 없으므로 부모를 자기 자신으로 만들어 줍니다.

var computers: Int = Int(readLine()!)!
var connection: Int = Int(readLine()!)!

var parents: [Int] = [Int]()

for index in 0 ... computers {
    parents.append(index)
}

그 다음엔 차례로 입력되는 두 노드를 연결해줍니다.

while connection != 0 {
    
    let input: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }
    var u: Int = input.first!
    var v: Int = input.last!
    
    union(&u,&v)
    connection -= 1
}

그리고 1번 컴퓨터가 바이러스에 걸렸으므로 1번과 연결된 노드의 갯수를 찾습니다.

var result = 0
var one = find(1)
for index in 2 ... computers {
    if one == find(index) {
        result += 1
    }
}

자 이제 핵심 로직이 union과 find를 한 번 살펴봅시다.

func union(_ x: inout Int, _ y: inout Int) {
    
    x = find(x)
    y = find(y)
    
    if x != y {
        parents[y] = x
    }
}

x와 y의 부모를 찾아주고 부모가 같지 않다면 연결해줍니다.

그럼 부모를 찾는 여정을 떠나봅시다.

func find(_ x: Int) -> Int {
    if x == parents[x] {
        return x
    } else {
        let y = find(parents[x])
        parents[x] = y
        return y
    }
}

처음에 자기자신을 부모노드로 정했기 때문에 진짜 부모는 자기 자신을 가지고 있을껍니다.

따라서 x랑 parents[x]랑 같은 값을 가지고 있으면 진짜 부모 이므로 x를 리턴 해주면 됩니다.

만약 그렇지 않다면 재귀호출을 통해서 진짜 부모를 찾아주고 그 값을 리턴하면 됩니다.

이렇게 작성된 코드를 제출하면 통과하실 수 있습니다.

 

다음 시간에 다른 알고리즘이나 다른 유니온 파인드 문제를 풀어보도록 하겠습니다.