weights = [(1, 0, 9), (0, 2, 10), (1, 3, 10), (1, 4, 5),
           (6, 1, 3), (2, 3, 9), (2, 4, 7), (2, 5, 2),
           (3, 5, 4), (3, 6, 8), (4, 6, 1), (5, 6, 6)]
weights.sort(key=lambda t: t[2])  # 가중치를 기준으로 정렬

mst = []
N = 7
p = []
# p 에는 정점의 개수만큼 인덱스(0~6)가 들어가 있다.
# 상호배타적 집합?(Disjoint set)이란
# 중복된 원소(공통 원소)를 갖지 않는 둘 이상의 집합을 의미한다.
# 집합간의 교집합이 없다 -> 구성되는 원소들은 중복될수 없다를 의미
# 왜 disjoint set 의 개념이 union-find 알고리즘과 동일하게 쓰이는걸까?
# disjoint, 서로소인 요소로 이루진 집합 자료구조라는 의미라고 한다.
# union-find 는 기본적으로 item 과 item 을 하나로 root 값으로 합치는 방법이다.
# 같은 집합의 요소인 2개 item 은 1개의 root 로 식별된다.
# 이미 같은 root 를 가르키는 item 들이 있다면 그것은 같은 집합에 속한다는 것을 의미한다.
# kruskal 에서는 합집합에 속한 두 item 을 연결하게되면 cycle 이 일어나게된다.
# 직관적으로 이미 같은 집합안에 있는 두 요소를 또다시 합집합으로 묶는다는 것은 말이 안된다.
# cycle 이 일어나게되면 최소 간선(N -1)으로 모든 정점을 연결 할 수 없다.
# 따라서 최소간선으로 연결하기위 union-find 의 합집합, 부모찾기 연산을 이용한다.
# 이 알고리즘에서 같은 값을 공유하지 않는다는 말은?
# 모든 정점을 '연결'한다는 의미는
# 모든 정점이 '하나의 루트'를 갖게 한다는 것을 의미한다.
# 따라서 연결을 마친다면 집합의 갯수는 1개가 되고 root 또한 1개가 된다.

for i in range(N):
    p.append(i)


def find(u):
    # if 문 없이 return p[u] 만 있어도 같은 결과를 도출한다
    # 그렇다면 왜 if 의 find() 재귀과정이 필요한걸까?
    # 이는 경로압축, 최적화를 위한 코드다. 효율성을 위한 코드
    # 재귀를 통해 root 를 할당해주지 않는다면 나중에는 연결리스트가 길게 늘어진
    # 형식으로 트리구조가 짜일수도 있기 때문이다.
    # 트리 깊이를 줄이고 부모노드가 아닌 root 를 할당해줌으로써 검색연산을 줄인다.
    if u != p[u]:
        p[u] = find(p[u])
    return p[u]


def union(u, v):
    root1 = find(u)  # 너희 부모님(or root), 내 부모님 찾아오자
    root2 = find(v)
    p[root2] = root1  # 연결, 합집합 해주는 코드


tree_edges = 0
mst_cost = 0
while True:
    if tree_edges == N - 1:  # edge 의 수는 무조건 N -1
        break
    u, v, wt = weights.pop(0)  # 가중치(wt)가 작은 item 부터 정렬대상이 된다.
    if find(u) != find(v):
        union(u, v)
        mst.append((u, v))

        # wt 를 유일하게 계산하는 부분,
        # 가중치를 고려한다를 코드로 이행한 부분.
        # 생각보다 길고 복잡한 코드를 필요로 하지 않는다.
        # 단지 가중치가 낮은 edge 부터 연결을 고려하는 것 뿐이다.
        # 아마도 이런 특성이 greedy 하다는 것이 아닐까?
        # 전체의 모습을 고려했을 때 현 단계에서 가중치의 값이 작은 edge 를 선택하는 것 보다
        # 가중치가 크더라도 전체 graph 의 가중치를 줄여주는 경우의 수가 있지 안을까?
        # '지역적'으로 greedy 하다는 의미가 이런 말 같다.
        mst_cost += wt
        tree_edges += 1  # 모든 정점 연결을 위해 필요한 edge 수는 N -1

print('최소신장트리: ', end='')
print(mst)
print('최소신장트리 가중치: ', mst_cost)

if __name__ == '__main__':
    pass
