최소 신장 트리 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 5249

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYHO7a2JoDFAVT#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다. 0번부터 V번까지의 노드와 E개의 간선을 가진 그래프 정보가 주어질 때, 이 그래프로부터 최소신장트리를 구성하는 간선의 가중치를 모두 더해 출력하는 프로그램을 만드시오.

 

입력

첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 마지막 노드번호 V와 간선의 개수 E가 주어진다. 다음 줄부터 E개의 줄에 걸쳐 간선의 양 끝 노드 n1, n2, 가중치 w가 차례로 주어진다.  1<=T<=50, 1<=V<=1000, 1<=w<=10, 1<=E<=1000000

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 2 3 0 1 1 0 2 1 1 2 6 4 7 0 1 9 0 2 3 0 3 7 1 4 2 2 3 8 2 4 1 3 4 8 4 6 0 1 10 0 2 7 1 4 2 2 3 10 2 4 3 3 4 10	#1 2 #2 13 #3 22

---

2. 문제풀이

MST문제이기 때문에 크루스칼 혹은 프림알고리즘으로 풀면된다. 나는 구현이 쉬운 크루스칼 알고리즘을 이용하여 문제를 풀었다. 크루스칼 알고리즘은 싸이클이 생기지 않는내에서 제일 가중치가 적은 간선들부터 선택하여 연결하여 MST를 완성하는 그리디 알고리즘이다.

---

3. 소스코드

#D4 5249 최소 신장 트리
 
#부모가 누구인자 가져오는 함수
def get_parent(x):
    if parent[x] != x: parent[x] = get_parent(parent[x])
    return parent[x]
 
#부모를 병합하는 함수
def union_parent(x, y):
    a = get_parent(x)
    b = get_parent(y)
    if a > b: parent[a] = b
    else: parent[b] = a
 
#부모가 같은지 비교하는 함수
def find(x, y):
    return get_parent(x) == get_parent(y)
 
 
for t in range(int(input())):
    answer = 0
    V, E = map(int, input().split())
    #부모가 누구인지 저장하는 변수
    parent = [i for i in range(V+1)]
    #연결된 노드와 가중치를 저장하는 변수
    edge = [list(map(int, input().split())) for _ in range(E)]
    #가중치를 기준으로 정렬(뒤에서 꺼내야 비용이 적으므로 내림차순 정렬)
    edge.sort(key=lambda x: -x[2])
    #간선이 빌때까지 반복
    while edge:
        #데이터 꺼내서
        a, b, v = edge.pop()
        #부모가 다른경우만(싸이클이 안생기는 경우)
        if not find(a,b):
            #부모를 병합한다.
            union_parent(a, b)
            #정답에 값을 더한다.
            answer += v
 
    print('#{} {}'.format(t+1, answer))