최소 스패닝 트리를 이용해서 그래프를 두 집합으로 분리하기(크루스칼 알고리즘 미세팁)

1. 문제

 

1647번: 도시 분할 계획 (acmicpc.net)

1647번: 도시 분할 계획

 

2. 풀이

 

입력 자체가 "임의의 두 집 사이에 경로가 항상 존재하는 입력이 주어진다"라고 되어있는데

 

맨 처음에는 모든 정점에 대하여 서로 연결된 하나의 그래프 집합이 주어지는데..

 

여기서 몇개의 간선을 선택해서 두 집합으로 분리하라는 문제

 

이 때 선택된 간선의 가중치 합이 최소가 되도록 만들어야한다

 

최소 스패닝 트리 이전에 그냥 진짜 단순하게 생각해보면, 초기에는 하나의 간선도 선택하지 않으니까 

 

전체 그룹의 수는 n개가 있는데

 

매번 가중치가 최소인 간선을 선택해서 union을 시키는데 성공하면, 두 정점이 하나의 그룹이 되므로..

 

전체 그룹의 수가 1개씩 줄어든다

 

그러면 이런 방식으로 매번 가중치가 최소인 간선을 선택해 union을 시키는데,

 

그룹 수를 1개씩 줄여가면서.. 최종적으로 그룹 수가 1개일때 선택한 모든 간선의 가중치 합에,

 

마지막으로 선택된 간선의 가중치를 빼주면 그룹이 2개가 되잖아?

 

#그래프 정점들을 두 집합으로 분리하기

from sys import stdin

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

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

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

n,m = map(int,stdin.readline().split())

edges = []

answer = 0

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    edges.append((c,a,b))

edges.sort()

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

#초기에는 그룹의 수가 정점의 수인 n개만큼 있다
g = n

for c,a,b in edges:
    
    if find_parent(a,parent) != find_parent(b,parent):
        
        union(a,b) # 두 정점을 union 시키면... 하나의 그룹이 되므로..
        answer += c
        
        g -= 1 #그룹의 수가 1개씩 줄어든다..

    if g == 1: #매번 간선을 고르다가, 그룹이 1개가 된다면...
        
        answer -= c #마지막으로 선택된 간선을 제거하고 break
        break
    
print(answer) #그러면 전체 그룹의 수는 2개가 되고, 이때 선택된 간선 가중치 합이 정답

 

 

"최소 스패닝 트리"라는건 모든 정점이 서로 연결되면서 가중치 합이 최소가 되도록 만든 트리인데

 

동일하게 생각하면 결국 선택한 간선의 수가 n-1개가 된다면 "모든 임의의 두 정점이 서로 연결된 하나의 집합"이 되므로

 

n-2개만 선택한다면 n-1개의 정점이 서로 연결된 하나의 집합, 1개의 정점만이 서로 연결된 하나의 집합으로 분리되면서

 

전체 선택된 간선 가중치 합을 최소로 만들 수 있다

 

두 집합으로 가중치 합이 최소가 되게 분리한 그래프야 여러개 있을 수 있겠지만.. 이렇게하면 확실하게 하나는 구할 수 있다는거지

 

결론은 n-2개의 간선을 선택한 최소 스패닝 트리가 정답

 

#그래프를 두 집합으로 분리하기
from sys import stdin

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

def union(a,b,parent):

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

n,m = map(int,stdin.readline().split())

edges = []

answer = 0

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    edges.append((c,a,b))

#edges.sort()를 하면, (c,a,b)에서 c가 동일하면 a를 기준으로 정렬하므로
#시간이 조금 느려진다
#크루스칼 알고리즘에선, 첫번째 간선 가중치만을 기준으로 정렬하면 되니까.. 

#다음과 같이 하면 조금 시간확보 가능
edges.sort(key=lambda x: x[0])

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

count = 0

#n-2개의 간선을 선택한 최소 스패닝 트리를 만들면, 
#각 집합 내 정점이 서로 연결된 두 집합으로 분리된다
for c,a,b in edges:
    
    if count == n-2: #간선이 1개만 있는 그래프때문에 count == n-2를 먼저 써줘야함
        
        break
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)
        
    if a != b:
        
        union(a,b,parent)
        answer += c
        
        count += 1
    
print(answer)

 

 

몇가지 짚고 넘어가면.. 크루스칼 알고리즘에서 간선 리스트를 정렬할때, 첫번째 원소만을 기준으로 정렬하면

 

이게 이 문제에서 1초정도 빠르다

 

edges.sort()만 하면.. (c,a,b)에서 c가 동일할때 a를 기준으로도 정렬해버리니까 쓸데없는 부분을 정렬해서 낭비

 

크루스칼 알고리즘에서 a,b는 정렬할 필요 없거

 

#edges.sort()를 하면, (c,a,b)에서 c가 동일하면 a를 기준으로 정렬하므로
#시간이 조금 느려진다
#크루스칼 알고리즘에선, 첫번째 간선 가중치만을 기준으로 정렬하면 되니까.. 

#다음과 같이 하면 조금 시간확보 가능
edges.sort(key=lambda x: x[0])

 

 

이건 크게 시간에 영향 없는것 같기는 한디.. 다음과 같이 union 내에서 a,b의 find_parent를 하고

 

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

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

 

크루스칼 알고리즘에서 간선을 선택할때도 find_parent를 또 해버렸더라고??

 

for c,a,b in edges:
    
    if find_parent(a,parent) != find_parent(b,parent):
        
        union(a,b) # 두 정점을 union 시키면... 하나의 그룹이 되므로..
        answer += c
        
        g -= 1 #그룹의 수가 1개씩 줄어든다..

    if g == 1: #매번 간선을 고르다가, 그룹이 1개가 된다면...
        
        answer -= c #마지막으로 선택된 간선을 제거하고 break
        break

 

그래서 find_parent를 한번만 하게 다음과 같이 수정

 

def union(a,b,parent):

    if parent[a] > parent[b]:
        
        parent[a] = b
    
    else:
        
        parent[b] = a
        
#n-2개의 간선을 선택한 최소 스패닝 트리를 만들면, 
#각 집합 내 정점이 서로 연결된 두 집합으로 분리된다
for c,a,b in edges:
    
    if count == n-2: #간선이 1개만 있는 그래프때문에 count == n-2를 먼저 써줘야함
        
        break
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)
        
    if a != b:
        
        union(a,b,parent)
        answer += c
        
        count += 1

 

 

다음은 n = 2이고 m = 1인 그래프를 두 집합으로 분리하면.. 간선을 아무것도 선택 안해야하는데

 

습관적으로 if count == n-2를 마지막에 쓰면 오답

 

2 1
1 2 3

 

for c,a,b in edges:
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)
        
    if a != b:
        
        union(a,b,parent)
        answer += c
        
        count += 1
    
    if count == n-2: #간선이 1개만 있는 그래프때문에 count == n-2를 먼저 써줘야함
        
        break