[ProblemSolving] 백준 - 1197 최소스패닝트리(그래프)

문제 링크

문제 설명

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력1

3 3
1 2 1
2 3 2
1 3 3

예제 출력1

3

나의 풀이

크루스칼 알고리즘을 이용하는 문제다.

크루스칼과 그리디

MST(Minimum Spanning Tree)를 구현하기 위해 사용하는 알고리즘이다.

크루스칼은 사이클 이루지 않는 최소 비용 간선을 택하는 방법이며,

모든 정점을 최소 비용을 연결하는 최적의 값을 구하는 그리디 유형이다.

그리디는 그 순간에 가장 최적을 선택하므로, 전체적으로는 최적이 아닐 수 있다.

반면, 크루스칼은 MST를 이용해 최적의 해답을 준다.

크루스칼 동작

1. 가중치 오름차순 정렬

2. 정렬된 간선 리스트에서 사이클 형성하지 않는 간선 선택

   • 가장 낮은 가중치 먼저 선택
   • 사이클을 형성하는 간선을 제외

3.해당 간선을 현재의 mst(최소 비용 신장 트리) 집합에 추가

구현시 주의

1. 다음 간선 택하여 집합에 추가될 때, 사이클 생성하는지 체크

   • 추가할 새 간선의 양끝 정점이 같은 집합에 있으면 사이클 형성됨

2. 사이클 생성 여부 확인

   • union-find 알고리즘 적용

     union : 두 개의 집합을 하나의 집합으로 합치는 연산
     find : 루트까지 올라가는 경로 상의 각 노드의 부모 노드를 루트로 갱신,

   • 경로 압축이라고 부른다

코드

v, e = map(int, input().split())
graph = []
for i in range(e):
    a, b, c = map(int, input().split())
    graph.append((a, b, c))
graph.sort(key = lambda x: x[2]) #가중치 오름차순 정렬

mst = [] # 최소신장 트리 담는 리스트
p = [0] # 상호배타적 집합

for i in range(1, v+1):
    p.append(i) # 각 정점 자신이 집합의 대표

def find(u): # 각 노드의 루트 정점 찾기
    if u != p[u]:
        p[u] = find(p[u]) # 경로 압축
    return p[u]

def union(u,v):
    root1 = find(u)
    root2 = find(v)
    p[root2] = root1 # 결합. 두변수가 바뀌어도 됨
    
edges = 0 # 간선 개수
cost = 0 # 가중치 합

while True:
    if edges == v-1: # 크루스칼은 정점-1개의 간선을 선택
        break
    u, w, t = graph.pop(0) # 오름차순이니까 가중치작은 것부터 pop
    if find(u) != find(w): #u와 v가 서로 다른 집합에 속해 있으면
        union(u, w)
        mst.append((u, w))
        cost += t 
        edges += 1
print(cost) # 최소신장트리 가중치 합
#  print(mst) # 최소신장트리