Ray`s Tech Lab

신장 트리 (Spanning Tree) ? 

하나의 그래프가 있을 때 그 그래프의 모든 노드를 가지고 있으면서 사이클(Cycle)이 없는 부분 그래프(Sub graph)!

원래 그래프가 N개의 노드를 가진다면, 그 놈의 신장트리는 N개의 노드와 N-1개의 간선(edge)를 갖는다. (간선이 N - 1개보다 적으면 모든 노드가 연결돼있지 않고 N - 1개보다 많으면 사이클이 있는 그래프다).

최소 신장 트리?

신장 트리는 원본 그래프의 부분 그래프이므로 당연히 여러 개 존재할 수 있는데, 그 중 간선들의 가중치 합이 가장 적은 신장 트리를 최소 신장 트리(MST, Minimun Spanning Tree)라고 부른다.

크루스칼 알고리즘?

주어진 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 그리디 알고리즘의 일종으로, 이해하기 매우 쉬운 알고리즘이다. 

1. 가장 작은 가중치를 갖는 간선을 선택한다. 
2. 선택되지 않은 간선 중 가장 가중치를 갖는 간선을 선택한다
3. 그 간선이 기존에 선택했던 간선들과 사이클을 이루지 않는지 체크. 만약 사이클을 이룬다면 그 간선은 버린다.
4. 모든 노드들이 골라질 때까지 2 ~ 3을 반복

모든 노드들이 골라지는지의 여부는 노드들을 세도 되고, 선택된 간선의 개수가 N - 1개인지로 해도 되고, 아니면 그냥 모든 간선들에 대한 조회가 끝날 때까지 해도 된다. 매 페이즈마다 사이클을 이루지 않게끔 골라왔으니 이렇게 만들어진 서브트리는 신장 트리임이 보장되며, 또한 매 페이즈마다 항상 작은 가중치를 갖는 간선들을 골라왔으니 이렇게 만들어진 신장트리는 당연히 최소 신장 트리임이 보장된다.

가장 까다로운 작업은 사이클을 이루는지 판단하는 작업인데, 이는 유니온 파인드를 통해서 간단히 판별할 수 있다.

※ 유니온 파인드에 대해 정리했던 글

https://jofestudio.tistory.com/11

유니온 파인드로 사이클을 판별가능한 이유

유니온 파인드를 이용하면 무방향 그래프에서의 사이클 판별이 가능하다. 방향 그래프에서는 DFS를 통해 가능함. 근데 어떻게 가능한 걸까?

우선 다음 작업으로 사이클을 판단가능하다.

1. 간선을 고른다.
2. 그 간선들에 딸린(?) 노드 두 개가 있을 것이다. 그 두 놈이 같은 집합에 있는지, 즉 같은 그래프에 있는지 확인한다.
3. 두 놈이 다른 그래프에 있다면 두 노드에 대해 Union연산을 한다. 두 놈이 같은 그래프에 있다면 사이클이 있는 거다.

왜 이 작업으로 사이클 판단이 된다는걸까?

유니온 파인드는 집합에 대한 연산들로 생각할 수 있다. 유니온은 두 집합을 합치는거고, 파인드(흔히들 getParant라는 이름으로 메서드를 짓기도 함)는 특정 원소가 속한 집합을 알려주는 연산인 거다. 여기서, 그래프를 일종의 집합으로 볼 수 있다!

이 그래프에서 가장 작은 노드를 리더로 생각한다면 어떨까. 그럼 위 그래프에서의 리더는 0이다. 

1이 속한 그래프의 리더 = 0 이다.

5가 속한 그래프의 리더 = 0 이다.

이런 식으로, 그래프를 하나의 집합으로 표현가능한 것이다. 

이 그래프에서, 우선 처음에 다음과 같이 리더 테이블을 만들어줬다고 하자. 육안으로 세 놈이 같은 그래프에 있는 걸 당연히 확인가능하지만 일단 각자가 서로 다른 그래프에 있다고 생각하고 테이블을 초기화한다.

간선 (1, 2)를 골랐다. 두 노드가 같은 집합에 속하는지(즉 두 놈이 속한 집합의 리더가 같은지)를 보니까, 다르다. 그럼 두 놈을 Union해준다.

즉 이제 노드 1과 노드 2는 같은 집합, 즉 같은 그래프에 있다고 생각할 수 있다.

이번엔 간선 (1, 3)을 골랐다. 두 노드가 같은 집합에 속하는지를 보니까, 다르다. 그럼 두 놈을 Union해준다.

즉 이제 노드 1과 노드 3은 같은 집합 즉 같은 그래프에 있다고 생각할 수 있는 거다.

이제 간선 (2, 3)을 골랐다. 두 노드가 같은 집합에 속하는지를 보니까 같은 집합에 있다! 노드 2가 속한 집합의 리더와 노드 3이 속한 집합의 리더가 같기 때문이다. 따라서 처음에 그림으로 주어진 그래프가 사이클이 있다고 판별가능하다. 왜냐하면 간선 (2, 3)을 골랐다는 것 자체가 노드 2와 3은 서로 이어져있음을 의미하는 것이기 때문이다.

• 즉 노드 2와 노드 3이 서로 다른 집합이었다면, 이 둘을 이어도(둘 사이의 간선을 그린다고 생각) 사이클은 생기지 않음. 원래 둘이 속한 집합 즉 그래프가 겹치지 않는 것이었으니까!
• 그러나 노드 2와 노드 3이 서로 같은 집합이었다면..즉 둘 사이를 잇기도 전에 애시당초 같은 그래프 안에 있던 거라면 그 둘을 잇는다는 것은 사이클을 만드는 것이 되는 것임. 

따라서 유니온 파인드로 그래프의 사이클 판단을 내릴 수 있는 것이다.

그래서 크루스칼은 결국 다음과 같은 순서로 진행한다고 볼 수 있다

1. 가장 작은 가중치를 갖는 간선을 선택한다. 
2. 그 간선에 딸린 두 노드가 같은 집합인지 판단(즉 두 노드의 리더를 비교)
3. 같은 집합이면(두 노드의 리더가 같다면) 그 간선을 선택하지 않음. 5로 건너뜀
4. 다른 집합이면(두 노드의 리더가 다르면) 그 간선을 선택. 두 노드는 union연산해줌
5. 그 다음으로 작은 가중치를 갖는 간선을 골라 2부터 반복. 모든 노드들이 골라질 때까지!

분리집합(Disjoint Set)이란 서로 중복되지 않는 부분집합들로 나뉜 원소들에 대한 정보를 다루는 자료구조이다. Union-Find 알고리즘은 이 자료구조를 활용하는 대표적인 그래프 알고리즘 중 하나로, '합집합을 찾는다'라는 의미를 가진다. 디테일하게 들어가면 원소 x, y를 고른 다음 x가 속한 집합과 y가 속한 집합이 같은지 판별하는 알고리즘안대, 이는 여러 노드가 존재할 때 내가 선택한 임의의 두 노드가 서로 같은 그래프에 속하는지 판별한다는 것과 같은 개념으로 생각할 수 있다.

그냥 내가 이해한대로 쉽게(나름대로) 설명하자면, Union-Find알고리즘과 분리집합은 집합을 표현하는 하나의 형태이다. 1부터 5까지의 원소들이 있고 이들이 각각 집합의 형태를 이루고 있다고 하자. 즉,

{1}, {2}, {3}, {4}, {5}

이렇게 있는 것이다. 근데 이를 표를 통해 다음과 같이 표현할 수 있다.

{1}의 입장에서 자기가 속한 집합의 리더는 자기 자신(1)이고, {2}나 다른 애들 입장에서도 마찬가지다. 즉 표를 통해 자신이 속한 집합의 리더를 나타내준것! 근데 여기서 {1}과 {2}가 만나서 합집합 {1, 2}를 만들어냈다고 하자. 1과 2가 같은 집합의 원소로 구성된 것이다. 현재 존재하는 집합들은

{1, 2}, {3}, {4}, {5}

인 것이다. 이는 방금과 같은 표를 통해 어떻게 표현할 수 있을까?

다른 건 변함없고 2만 변화가 생겼다. 자신이 속한 그룹의 리더가 1이 된 것! 사실 뭐 2를 리더로 할 수도 있지만..집합을 이루는 원소 중 가장 작은 놈을 리더로 뽑는 것이다. 쉽게 생각해서 2는 1이 이끄는 집합의 멤버가 된 것이라고 생각해도 된다. 만약 다른 애들도 서로 합치고 지지고 볶고 해서 집합들이 다음과 같이 됐다면?

{1, 2}, {3, 4, 5}

표는 다음과 같아질 것이다.

그럼 생각해보자. 내가 임의로 두 원소를 뽑았는데 그 놈이 2랑 4다. 이들이 각각 속한 집합은 같은가?

표를 통해서 다르다는 것을 알 수 있다. 왜 Why? 2는 1이 이끄는 집합에 속해있고, 4는 3이 이끄는 집합에 속해있기 때문이다. 서로가 속한 집합의 리더가 다르기 때문에 이들이 속한 집합은 서로 다른 집합이다라고 말할 수 있는 것이다. 이것이 Union-Find알고리즘이다. 

근데 Union Find알고리즘은 여러 노드가 존재할 때 두 노드를 선택해서 이 두 녀석이 같은 그래프에 속하는지 판별하는 것으로도 이해할 수 있다고 했다. 간단하다. 단지 집합으로 표현하던 걸 그래프로 나타낼 때 Union Find가 저렇게 표현될 뿐이다. 1~5까지의 각 원소들이 집합의 형태를 이루고 있는 상태를, 1~5까지의 노드들이 서로 연결되지 않고 존재하는 상태라고 이해하면 된다. 그리고 집합들이 합쳐지는 것은 노드들 간에 연결선이 생겨서 연결되는 것으로 생각하면 된다. 따라서 내가 고른 임의의 두 노드가 서로 같은 그래프에 존재하는지 확인하는 것은 각각의 root노드들을 확인해서 같으면 같은 그래프 상에 존재하는 것이다! ...사실 이 부분은 글로만 써서 이해가 잘 안 될 수도 있으니 공부할 때 참고한 나동빈 님의 영상을 링크로 걸어두겠다.

https://www.youtube.com/watch?v=AMByrd53PHM 

그럼 Union Find를 파이썬으로 구현해보자.

parant = [i for i in range(n + 1)]

def getParant(x):         # x의 부모를 리턴하는 함수
    if parant[x] == x:    # x의 부모가 자기자신이라면 x를 그대로 리턴
        return x        
    parant[x] = getParant(parant[x])  # x의 부모가 자기자신이 아님 -> 재귀호출로 x의 부모 재설정
    return parant[x]                  # 최종적으론 x의 부모 리턴
    
def union(x, y):        # x가 속한 집합과 y가 속한 집합 합치기 - 가장 부모을 비교해 더 작은 쪽으로 합침
    x, y = getParant(x), getParant(y)
    if x < y:           # x가 더 작으니까 y의 부모를 x로
        parant[y] = x
    elif x > y:         # y가 더 작으니까 x의 부모를 y로
        parant[x] = y

def hasSameParant(x, y):         # x, y가 같은 부모를 같는지 즉 같은 집합에 속해있는지
    x, y = getParant(x), getParant(y)
    if x == y:
        return "YES"
    else:
        return "NO"

리더로 표현하던 것을 부모로 표현하는 것에만 차이가 있다. getParant함수가 이 알고리즘의 핵심으로 자신의 부모가 자기자신이 아니라면 재귀호출을 통해 자신의 부모를 최상단 노드, 즉 집단 내에서 가장 작은 놈으로 설정해준다.  이를 통해 백준 사이트에서 대표적으로 다음과 같은 문제를 풀 수 있다.

https://www.acmicpc.net/problem/1717