My code
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n, m = map(int,input().split())
parent = [0] * (n + 1)
edges = []
for i in range(1, n + 1):
parent[i] = i
for i in range(m):
a, b, cost = map(int,input().split())
edges.append((cost, a, b))
edges.sort()
result = 0
final = 0
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
final = cost
print(result - final)
Answer
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int,input().split())
parent = [0] * (v + 1)
edges = []
result = 0
for i in range(1, n + 1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int,input().split())
edges.append((cost, a, b))
edges.sort()
last = 0
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
last = cost
print(result - last)
Code Review
이번 문제는 N 개의 집과 그 집들을 연결하는 M 개의 길이 있는 마을이 있다고 할 때, 두 집 사이에 경로가 항상 존재하게 하면서 길을 없애 마을을 2개로 분리한 후 길을 없애고 남은 길들의 유지비 합의 최소값을 구하는 것이었습니다.
이 문제에서 집은 그래프의 노드, 집들을 연결하는 길은 그래프의 간선이라 여기고 길마다의 유지비를 간선 비용이라 여겼을 때 간선을 없애고 남은 간선들 비용의 최소값을 구하는 것이므로 최소 신장 트리를 구하는 문제라고 생각할 수 있습니다. 최소 신장 트리를 구하는 알고리즘 중 크루스칼 알고리즘을 이용하여 문제를 해결했습니다.
먼저 find_parent 함수를 이용하여 특정 원소가 속한 집합을 찾도록 해주었고 union_parent 함수를 이용하여 두 원소가 속한 집합을 합치도록 해주었습니다. 그리고 모든 간선에 대한 정보를 입력 받고 비용순으로 이를 오름차순으로 정렬시켜주었습니다.
따라서 간선을 작은 것부터 하나씩 확인해가며 사이클이 발생하지 않는 경우에만 집합에 포함시켜주고 그 cost 를 더해주었습니다.
이때, 주의해야 할 점은 마을을 2개로 분리한다는 사실입니다. 만약 이 조건을 간과하고 위의 과정만 수행한다면 마을은 2개가 아닌 최소 신장 트리 1개 즉 1개의 마을이 됩니다. 따라서 최소 신장 트리를 2개로 분리하려면 최소 신장 트리에서 비용이 가장 큰 간선 하나를 삭제해주면 됩니다.
간선을 비용에 따라 오름차순으로 정렬했기 때문에 반복문에서 사이클이 발생하지 않는 경우의 마지막에는 최소 신장 트리의 간선 중 가장 큰 비용에 해당하는 간선의 비용이 저장 됩니다. 따라서 그 값을 final 변수에 저장해준 뒤 최종 결과 result 에서 빼주어 출력해주었습니다.
댓글