[Python] 백준 1922 네트워크 연결 | 크루스칼 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

 

문제 해결 포인트

- 크루스칼 알고리즘 (최소 스패닝 트리 알고리즘)

- 서로소 집합을 위한 find_parent, union_parent 함수

- edges : 간선 비용, 간선a, 간선b를 저장하여 오름차순으로 저장

- parent : 각 정점 별 집합 정보 저장

 

- 정렬된 edges 를 하나씩 방문하며 사이클이 발생하지 않는다면 간선 연결

    - find_parent(a) != find_parent(b)   즉, 같은 집합에 속해있지 않다

 

 

 

작성 코드

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())

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

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


parent = [i for i in range(N+1)]
edges = []

for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

edges.sort()
result = 0
for c, a, b in edges:
    if find_parent(a) != find_parent(b):
        union_parent(a, b)
        result += c

print(result)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚