골드4

문제 1647

해당 문제 링크

정답

## 도시 분할 계획

import sys
sys.setrecursionlimit(10**6)

input=sys.stdin.readline

def find(x):
    if parent[x]!=x:
        parent[x]=find(parent[x])
    return parent[x]

def union(a, b):
    a=find(a)
    b=find(b)

    if a<b:
        parent[b]=a
    else:
        parent[a]=b

n, m= map(int, input().split())

parent=[i for i in range(n+1)]

# 간선 정보 담을 리스트와 최소 신장 트리 계산 변수 정의
edges=[]
res=[]

# 간선 정보 주어지고 비용을 기준으로 정렬
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

# 간선 정보 비용 기준으로 오름차순 정렬
edges.sort()

# 간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행
for e in edges:
    c, a, b = e
    # find 연산 후, 부모 노드 다르면 사이클 발생하지 않으므로 union 연산 수행 -> 최소 신장 트리에 포함!
    if find(a) != find(b):
        union(a, b)
        res.append(c)

print(sum(res[:-1])) #비용이 가장 큰 간선을 지워야 하기 때문에 가장 큰 유지비가 드는 간선 제외하고 유지비의 합을 구함

풀이

런타임 에러 및 시간 초과가 많이 난 문제였다.

이전 문제에서 시간을 줄일 수 있는 방법은 다 적었지만 해결이 안되었다.

아래 코드 부분이 문제였다.
각 집합에 포함되어있는 가중치들을 리스트에 넣고 가장 큰 가중치를 제외하고 합쳐서 연산하면 되는 계산인데
시간 내에 풀리는 코드는 아래와 같다.

for e in edges:
    c, a, b = e
    # find 연산 후, 부모 노드 다르면 사이클 발생하지 않으므로 union 연산 수행 -> 최소 신장 트리에 포함!
    if find(a) != find(b):
        union(a, b)
        res.append(c)

print(sum(res[:-1])) #비용이 가장 큰 간선을 지워야 하기 때문에 가장 큰 유지비가 드는 간선 제외하고 유지비의 합을 구함

아래와 같이 작성하면 시간초과에 걸리게 된다.

# 간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행
for i in range(m):
    c, a, b = edges[i]
    # find 연산 후, 부모 노드 다르면 사이클 발생하지 않으므로 union 연산 수행 -> 최소 신장 트리에 포함!
    if find(a) != find(b):
        union(a, b)
        total_cost+=total_cost
        max_cost=max(c, max_cost)

print(total_cost-max_cost) #비용이 가장 큰 간선을 지워야 하기 때문에 미리 저장해둔 max_cost값을 빼준다.

어차피 이전에 sort로 정렬하고 작은 값부터 들어가기 때문에 가장 마지막에 나오는 값이 클 것이다 이를 제외하는 식이 더 간단하고 빠를 것이라고 생각이 든다!