백준-1197-최소 스패닝 트리

문제

최소 스패닝 트리

풀이

1. 문제조건 해석

   최소 신장 트리(MST)문제.

2. 알고리즘

   • Kruskal 알고리즘을 사용했다. $O(E\log{E})$
     • 간선 정렬에만 시간복잡도 사용됨
     • Disjoint Set에 대한 Union-find 연산이 핵심이다
       • 배열을 사용하면 시간복잡도 $N$ 곱해짐
       • 재귀를 사용하면 시간복잡도 추가 없음
3. 코드

    ### O(E^2*N) ###
    from sys import stdin
    input = stdin.readline
   
    n, e = [int(x) for x in input().rstrip().split()]
   
    # Kruskal - 가중치가 낮은 간선부터 선택. 
    # 간선에 연결된 노드 둘 다 선택되어 같은 집합이면 선택하지 않는다.
    # 다른 집합이면 간선 선택
   
    edges = []
    disjoint_set = [_ for _ in range(n+1)] 
    # disjoint_set[i] : i번 노드는 disjoint_set[i]번 노드의 집합에 속한다
    for _ in range(e):
        edges.append([int(x) for x in input().rstrip().split()])
           
    def union_find(u, v, disjoint_set):
        '''
        u노드와 v노드가 같은 집합에 있으면 그대로
        다른 집합에 있으면 union
        '''
        if u > v:
            v, u = u, v
        if disjoint_set[u] == disjoint_set[v]: # 같은 집합에 있으면
            return False
        elif disjoint_set[u] != disjoint_set[v]: # 다른 집합에 있으면
            for i, s in enumerate(disjoint_set):
                if s == disjoint_set[v] and i != v:
                    disjoint_set[i] = disjoint_set[u]
            disjoint_set[v] = disjoint_set[u]
            return True
   
    edges.sort(key=lambda x:x[2])
    answer = 0
    for u, v, w in edges:
        if union_find(u, v, disjoint_set):
            answer += w    
    print(answer)
   

    ### heap과 재귀를 이용한 방법 O(ElogE) ### 
    from sys import stdin
    import heapq
    input = stdin.readline
   
    n, e = [int(x) for x in input().rstrip().split()]
   
    edges = []
    disjoint_set = [_ for _ in range(n+1)] 
    # disjoint_set[i] : i번 노드는 disjoint_set[i]번 노드의 집합에 속한다
    for _ in range(e):
        u, v, w = [int(x) for x in input().rstrip().split()]
        heapq.heappush(edges, (w, u, v))
           
    def find(u, disjoint_set):
        '''
        부모 노드를 찾는다.
        '''
        if u == disjoint_set[u]:
            return u
        # 부모 노드를 업데이트
        disjoint_set[u] = find(disjoint_set[u], disjoint_set)
        return disjoint_set[u]
    def union(u, v, disjoint_set):
        '''
        u노드와 v노드가 같은 집합에 있으면 그대로
        다른 집합에 있으면 union
        '''
        u = find(u, disjoint_set)
        v = find(v, disjoint_set)
        if u == v: # 같은 집합에 있으면
            return False
        # 다른 집합에 있으면
        disjoint_set[v] = u
        return True
   
    answer = 0
    while edges:
        w, u, v = heapq.heappop(edges)
        if union(u, v, disjoint_set):
            answer += w    
    print(answer)
   

4. 배운점

   • 부모 노드를 찾을 때 재귀를 이용해야 빠르다.
     • 트리 구조를 구현할 때 재귀를 사용하면 편하다.
   • 최소(최대)값을 반복적으로 접근할 때는 heap 고려하는 것 잊지 말자.