크루스칼 알고리즘
동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
-
입력
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M은 1 이상 1,000,000 이하인 정수이다.
그 다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C(1 <= C <= 1,000) 라는 뜻이다. -
출력
첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력한다. -
입력 예시
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4 -
출력 예시
8
# p300
#그래프에서 두 개의 최소신장트리를 만들어야 함
#그러므로 크루스칼 알고리즘 사용
def find_parent(graph, a):
if graph[a] != a:
graph[a] = find_parent(graph, graph[a])
return graph[a]
def union(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a > b:
parent[a] = b
else:
parent[b] = a
n, m = map(int, input().split())
parent = [0] * (n+1)
edges = []
result = []
for i in range(1, n+1):
parent[i] = i
for i in range(m):
a, b, c = map(int, input().split())
edges.append((c, a, b))
edges.sort()
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union(parent, a, b)
result.append(cost)
result.sort()
print(sum([i for i in result[:-1]]))그냥 크루스칼 알고리즘으로 최소신장트리를 만든 후 가장 비용이 큰 도로를 없애면 되는 간단한 문제였다. 하지만 최소신장트리에 대한 개념이 명확하지 않아서 만약 도로를 없앴을 때 노드 하나만 남게되면 이게 최소신장트리가 맞는지 고민하는데 더 시간을 쓴 것 같다. 현재 이산수학을 수강중인데 나중에 교수님께 문의해봐야겠다.
+코스트를 일일이 result에 저장해놓고 이를 정렬한 뒤 인덱스 -1만 빼서 더하는 쓸데없는 방식을 썼는데, 그냥 교재에 나온대로
last = 0
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union(parent, a, b)
last = cost이렇게 반복문마다 최댓값을 갱신하는게 훨씬 깔끔한 것 같다.
