5.TIL - 신장트리, MST, 크루스칼, union-find

신장트리(Spanning Tree)

---

그래프 내의 모든 정점을 포함하는 트리(필연적으로 연결 트리이다.)

최소 연결 = 간선의 수가 가장 적다.

N개의 정점에서는 간선이 N-1개가 된다.

가장 적은 수의 케이블로 네트워크 링크 구축

사용 : N개의 정점을 최소의 케이블을 사용하여 연결하고자 하는 경우(통신 네트워크)

 

 

 

MST 최소신장트리(Minimun Spanning Tree)

---

신장트리에서 간선의 가중치 합이 최소인 트리

나올 수 있는 여러 개의 신장트리중에 간선의 가중치의 합이 가장 작은 트리

사이클이 포함되지 않는다!(신장트리 자체가 최소 간선이므로 사이클이 있을 필요가 없다.)

 

MST 구현 방법 - 크루스칼 알고리즘

 

간선을 선택하는 알고리즘

간선을 정렬한 뒤 작은 순서대로 선택(Greedy) 이 때, 사이클을 형성하는지 체크한다.

추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지 검사하면 된다.(union-find알고리즘)

 

MST 구축 방법에는 Prim알고리즘도 있는데 크루스칼은 간선을 선택, Prim은 시작 정점을 선택해서 단계적으로 확정해나가는 방법이다.

 

 

크루스칼 알고리즘 = 정렬(Greedy) + Union-find 

 

 

 

Union-Find 알고리즘(가장 중요)

---

서로 상호배타적인 집합(set)을 저장하고 조작하는 Disjoint Set을 표현하는 알고리즘.

집합을 구현하는 데는 많은 방법(비트 벡터, 연결 리스트, 배열)이 있으나 그 중 가장 효율적인 트리 구조를 이용한다.

 

Idea

위 사진처럼 "배열 인덱스 == 값"인 배열을 만들고 연결에 따라 인덱스 값을 루트(부모)로 바꿔준다.

 

 

방향은 고려해야할까? -> NO!

(1 -> 6), (6 -> 1) 처럼 입력되는 간선의 순서는 위 그림에서 그림 1)번과 그림 6)번을 참고하자. 연결만 되어 있다면 방향에 관계없이 어차피 부모는 하나의 인덱스로 합쳐진다. (만약 그림에서 Union(1, 6)이 었다면 6번 그림의 삼각 구조처럼 set가 형성 되었을 것.

 

초기화 배열의 값을(본인의 루트) 수정해나가며  x == root(x) 인 것은 본인이 뿌리 노드인 것이다. 

두가지만 기억하면 된다. Union 함수 , findRoot 함수

 

 

 

 

 

 

 

 

 

대표문제 프로그래머스 - 섬연결하기 : https://programmers.co.kr/learn/courses/30/lessons/42861

def solution(n, costs):
    root = [i for i in range(n)]
    answer = 0

    #최종 root를 반환
    def findRoot(x):
        if root[x] == x:
            return x
        else:
            return findRoot(root[x])
	
    #주어진 데이터에서 연결된 a -b를 연결해 합치고(Union)루트를 넣어준다.
    def union(a, b):
        a = findRoot(a)
        b = findRoot(b)

        root[a] = b





	#문제풀이
    costs.sort(key=lambda x: x[2])

    for i in costs:
        if findroot(i[0]) == findroot(i[1]):
            continue
        else:
            union(i[0], i[1])
            answer += i[2]

    return answer

print(solution(5, [[0,1,1],[0,2,2],[1,2,5],[1,3,3],[2,3,8],[3,4,1]]))