Kruskal (MST): Really Special Subtree

Problem Link
https://www.hackerrank.com/challenges/kruskalmstrsub/problem?isFullScreen=true

✅ Problem Summary

크루스칼 알고리즘(Kruskal's algorithm)를 이용한 최소 신장 트리(Minimum spanning tree) 탐색 문제

---

🧮 Applied Theory & Algorithm

1. 크루스칼 알고리즘(Kruskal's algorithm)

그림 출처: Wikipedia

---

📑 My Answer

• 모든 테스트 케이스 통과
• 참고 코드

def graph_info(g_nodes, g_from, g_to, g_weight):
    parents = [i for i in range(g_nodes+1)]
    edges_info = [(g_weight[i], g_from[i], g_to[i]) for i in range(len(g_from))]
    edges_info.sort()
    return parents, edges_info

def find_parent(parents, n):
    if parents[n] != n:
        parents[n] = find_parent(parents, parents[n])
    return parents[n]

def union_parent(parents, up, vp):
    if up < vp:
        parents[vp] = up
    else:
        parents[up] = vp
    return parents

def kruskal(g_nodes, g_from, g_to, g_weight):
    parents, edges_info = graph_info(g_nodes, g_from, g_to, g_weight)
    total_weights = 0
    for w, u, v in edges_info:
        u_parent, v_parent = find_parent(parents, u), find_parent(parents, v)
        if u_parent != v_parent:
            parents = union_parent(parents, u_parent, v_parent)
            total_weights += w
    return total_weights

📌 코드 구현 설명

• graph_info 함수에서 간선(edge) 정보를 저장한 edge_info와 서브 트리(subtree)의 루트 노드 정보를 저장할 parents 리스트를 생성한다.
  • 가중치가 작은 간선을 선택해나가는 방법인 크루스칼 알고리즘을 구현하기 위해 edge_info 생성후, 간선 가중치(weight)를 기준으로 오름차순으로 정렬
  • parents는 우선 노드 본인으로 초기화 (이후 서브 트리를 만들며 갱신)
• 가중치를 기준으로 오름차순 정렬된 edge_info의 간선들을 탐색하며 서브 트리를 만들어감
  • 트리의 사이클 여부를 확인하기 위해, 간선을 선택할 때마다 parents에서 해당 노드(node)의 루트(root) 노드를 확인
  • 루트 노드가 같지 않다면, parents에 저장된 각각의 루트 노드 번호 중 작은 값으로 갱신
• 모든 간선 탐색 후 종료

---