최소 스패닝 트리_1197

박상민·2024년 5월 31일
0

백준

목록 보기
27/36
post-thumbnail

문제

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

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

입력

첫째 줄에 정점의 개수 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

문제 아이디어

스패닝 트리란, 모든 노드들 간의 서로 연결은 되어있되 사이크링 존재하지 않는 부분 그래프를 의미한다.

최소 스패닝 트리 ⊂ 스패닝 트리

이처럼 최소 스패닝 트리는 가중치의 합을 최소로 하는 스패닝 트리를 말한다.

이 문제를 해결하기 위해 가장 많이 사용되는 알고리즘은 Kruskal 알고리즘이다.

Kruskal 알고리즘

  • Kruskal 알고리즘 의 동작과정
  1. 주어진 모든 간선 정보에 대해 오름차순으로 정렬 수행
  2. 정렬된 간선 정보를 하나씩 확인하면서 낮은 간선부터 순회하면서
  3. 사이클을 발생시키는지 확인한다.
  • 사이클을 발생시킨다면, continue
  • 사이클을 발생시키지 않는다면 추가한다.
  1. 1~3번의 과정을 모든 간선 정보에 대해 반복 수행 후, 추가된 간선들이 바로 최소 신장 트리이다.

1197문제의 경우 최소 스패닝 트리 문제는 정점도 많고, 가중치가 음수가 될 수 있을 뿐 아니라, 근본적으로 스패닝 트리를 만드는 과정에서 간선이 바뀔 수 있기 때문에 Union-Find 활용

  • Union-Find(쉽게 말하자면 모든 값이 자기 자신을 가리키도록 말하는 것)
    위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해봅시다. 이때 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때 모든 값이 자기 자신을 가리키도록 만드는 것,
    첫번째 행은 노드 번호, 두번째 행은 부모의 행을 의미

위와 같이 1과 2과 연결되어 있고 나머지 노드들이 자유 분방하게 존재한다고 생각해봅시다.


위와 같이 2번째 인덱스의 값에 1이 들어가는 것을 표현하여 연결성을 표현할 수 있다.(일반적으로 부모를 합칠 때에는 더 작은 값쪽으로 합친다)이것이 바로 Union-Find이다.


코드

import sys
input = lambda: sys.stdin.readline().rstrip()

V, E = map(int, input().split())

# Kruskal Algorithm
# https://techblog-history-younghunjo1.tistory.com/262
edges = []
for _ in range(E):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))
edges.sort(key=lambda x: x[2]) # C(Cost)가 적은 것부터 정렬


# Union-Find
parent = [i for i in range(V+1)]

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x]) # get_parent 거슬러 올라가면서 parent[x] 값도 갱신
    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if a < b: # 작은 쪽이 부모가 된다. (한 집합 관계라서 부모가 따로 있는 건 아님)
        parent[b] = a
    else:
        parent[a] = b        

def same_parent(a, b):
    return get_parent(a) == get_parent(b)


answer = 0
for a, b, cost in edges:
    # cost가 작은 edge부터 하나씩 추가해가면서 같은 부모를 공유하지 않을 때(사이클 없을 때)만 확정
    if not same_parent(a, b):
        union_parent(a, b)
        answer += cost
print(answer)
profile
I want to become a UX Developer

0개의 댓글