[백준] 1197번 최소 스패닝 트리 - Kruskal - union find

오픈 S/W 컨트리뷰톤과 카카오 코딩 테스트를 위해 열심히 알고리즘 공부를 하는 중이다.

한 문제를 풀기 위해 여러 개의 알고리즘을 공부하게 되니 시간이 오래 걸리는 것 같다.

간단하게 코드만 정리하고 다음 공부를 하러 가야겠다.

 

Kruskal과 Union Find

---

- Kruskal 알고리즘

최소 신장 트리(MST)를 만들 때 사용하는 알고리즘의 종류 중 하나다. 노드가 많고 산선이 적을 때 유리하다고 하는데, 최소 신장 트리를 만드는 알고리즘 중에서는 가장 쉽기 때문에 공부를 시작했다.

시간 복잡도는 ​ O(E * logV)

모든 간선을 비용의 오름차순으로 정렬한 다음 간선을 차례대로 선택한다.

 

- Union Find

서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

Kruskal 알고리즘에서 간선을 선택하는 과정에 적용할 수 있다.

 

코드 및 해설

---

 

import sys
input = sys.stdin.readline

#부모 노드를 찾는 함수
def getParent(arr, n):
    if arr[n] == n: return n
    return getParent(arr,arr[n])


#두 부모 노드를 합치는 함수
def unionParent(arr,n_1, n_2):
    a = getParent(arr,n_1)
    b = getParent(arr,n_2)
    if a < b : arr[b] = a
    else: arr[a] = b

#같은 부모를 가지는지 확인
def findParent(arr, n_1, n_2):
    a = getParent(arr,n_1)
    b = getParent(arr,n_2)
    if a==b: return 1
    else : return 0

edges = []
parent = {}
V, E = map(int,input().split())

#간선에 대한 정보를 입력받는다.
#문제에서 노드1, 노드2, 간선의 가중치 순으로 입력이 주어진다.
for _ in range(E):
    edges.append([*map(int,input().split())])

#부모노드 dict를 초기화 한다.
#모든 노드가 자기 자신을 부모노드로 지정하게된다.
for i in range(V):
    parent[i+1] = i+1

#가중치의 오름차순으로 간선을 정렬한다.
edges.sort(key=lambda val: val[2])

MST = []
#Kruskal's  Algorithm
for e in edges:
    v, u, w = e
    #두 노드의 부모노드가 같은지 비교하게 된다.
    if findParent(parent, v, u) == 0:
        #부모노드가 같지 않다면 두 노드를 연결해주고, 더 낮은 숫자를 가진 노드로 부모노드를 변경해준다.
        unionParent(parent,v,u)
        #최소 비용 신장트리의 결과 리스트에 현재 간선의 정보를 추가해준다.
        MST.append(e)
#문제의 답은 최소비용 간선트리의 "비용의 합" 이므로 출력 형식을 맞춰준다.
print(sum([w for v, u, w in MST]))

결과

---

한 문제를 푸는데 많은 시간이 소모되는 것 같다.

현재 나의 공부방법은

추천 알고리즘에 대한 개념을 찾아서 혼자 적용시켜보기 -> 복잡도를 줄이는 방법 찾아보기 -> 상위 제출자들의 정답 코드를 분석하여 부족한 점 찾기

순으로 진행하고 있다.

조금 더 효율적인 방법이 없을까..

 

참고 블로그