[백준/BOJ] gold4 - 1197번 최소 스패닝 트리 (Python)

▶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보다 작거나 같은 데이터만 입력으로 주어진다.

 

▶출력

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

 

▶예제

 

▶풀이

크루스칼을 이용해서 문제를 해결했다.

최소 스패닝 트리를 구하는 방식은 두 가지가 있는데

나는 크루스칼이 편해서 크루스칼로 풀었다.

다른 방식도 있기때문에 그게 편한 사람은 그걸로 풀면 될 것이다.

 

크루스칼의 기본 원리는 작은 weight의 edge부터 선택하는 것이다.

이때 cycle이 발생하게 되면 그 edge는 선택하지 않으면 된다.

이 부분은 union, find를 쓰면 되고, 작은 weight edge는 sort를 한 후에 선택해주면 된다.

# 크루스칼
def find(x):
    if x != root[x]:
        root[x] = find(root[x])
    return root[x]


v, e = map(int, input().split())
root = [i for i in range(v + 1)]
arr = []
for i in range(e):
    arr.append(list(map(int, input().split())))

arr.sort(key=lambda x: x[2])
answer = 0

for a, b, c in arr:
    aroot = find(a)
    broot = find(b)

    if aroot != broot:
        if aroot > broot:
            root[aroot] = broot
        elif aroot < broot:
            root[broot] = aroot

        answer += c

print(answer)

처음에 틀린 이유는 sort 해주는 과정을 거치지 않고 풀어서 틀렸다.

크루스칼에서는 작은 weight부터 선택해야 하기 때문에 sort가 필수다!!