| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 81092 | 35366 | 20079 | 40.990% |
문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
답안
import sys
v, e = map(int, sys.stdin.readline().split())
edges = []
for _ in range(e):
src, dest, weight = map(int, sys.stdin.readline().split())
edges.append((src, dest, weight))
result = 0
link = [i for i in range(v+1)]
def find(node):
if node == link[node]:
return node
result = link[node] = find(link[node])
return result
def union(a, b):
link[find(b)] = find(a)
edges.sort(key=lambda x: x[2])
for src, dest, weight in edges:
if find(src) == find(dest):
continue
union(src, dest)
result += weight
print(result)풀이
최소 스패닝 트리의 가중치를 구하는 문제로, 개념 이해가 필요하다면 아래 링크의 글 내용을 참고하자.
https://velog.io/@elon/최소-신장-트리MST-알고리즘-정리-Kruskals-Prims
나는 이 문제를 크루스칼 알고리즘을 이용해 풀었다.
edges.sort(key=lambda x: x[2])
for src, dest, weight in edges:
if find(src) == find(dest):
continue
union(src, dest)
result += weight
print(result)그래프는 (간선 시작점, 간선 끝점, 간선 가중치)[]의 형태로 입력받았고, 이름은 edges라고 했다.
이 상태에서 크루스칼 알고리즘을 적용하기 위해, edges를 가중치 오름차순으로 정렬한 뒤, 사이클이 만들어지지 않게 하면서 최대한 작은 가중치를 가지는 간선들을 사용해 MST를 만들도록 했다.
사용되는 간선들의 가중치(weight)을 result에 더해주면 문제에서 요구하는 MST의 가중치를 구할 수 있다.
