Kruskal Algorithm with Python

📖 문제 설명

문제 링크 : https://www.acmicpc.net/problem/1197

• 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
• 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

• 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
• 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다.
• 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

• 첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

💡 크루스칼 알고리즘에 대해

• 가장 적은 비용으로 모든 노드를 연결하는 알고리즘입니다.
• 가장 거리가 짧은 간선부터 집합에 포함시킵니다.
• 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않습니다.

🧑‍💻 코드 풀이

find-parent

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

• 부모노드를 찾아주는 로직입니다.

union-parent

def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)

    if a != b:
        parent[b] = a

• 부모노드를 서로 병합해주는 로직입니다.

input

parent = [i for i in range(n + 1)]
arr = []
for i in range(m):
    x, y, cost = map(int, sys.stdin.readline().split())
    arr.append([cost, x, y])
arr.sort()

• 입력값을 처리해주고 배열에 값을 할당해줍니다.
• cost를 기준으로 정렬해줍니다.

최소 가중치 찾기

answer = 0
for cost, x, y in arr:
    if find_parent(parent, x) != find_parent(parent, y) :
        union_parent(parent, x, y)
        answer += cost

print(answer)

• 부모가 같지 않을때 부모를 병합해줍니다.
• 부모가 병합될때 가중치를 지속적으로 answer 에 더해줍니다.
• 마지막으로 answer 를 출력해줍니다.