카테고리 없음

[백준/파이썬][Gold IV] 최소 스패닝 트리 - 1197

난쟁이 개발자 2024. 12. 31. 01:52
반응형

[Gold IV] 최소 스패닝 트리 - 1197

문제 링크

성능 요약

메모리: 124612 KB, 시간: 408 ms

분류

최소 스패닝 트리, 그래프 이론

제출 일자

2024년 12월 31일 00:56:23

문제 설명

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

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

입력

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

출력

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

풀이

Minimum Spanning Tree 로서, 흔히 최소 신장 트리로 알려져 있는 문제이다. MST는 가중치가 있는 연결 그래프에서 모든 정점을 연결하는 최소 비용의 트리를 찾는 문제이다. 

@코데풀 코드 소스를 보고 이런 알고리즘도 있다는 것을 알게되었다. 

크루스칼 알고리즘(위키백과)

그렇다면 이 문제를 해결해보자

def find(v) :
    if v != parents[v] :
        parents[v] = find(parents[v])

    return parents[v]

find(v) 

  • 목적: 주어진 정점 v의 부모 정점을 찾음.
  • 작동 원리:
    • 만약 v가 자신의 부모가 아니라면, 재귀적으로 부모를 찾음.
    • 경로 압축을 통해 v와 관련된 모든 정점들이 직접 부모를 가리키도록 최적화.
  • 결과: 집합의 루트 정점 반환.
def union(v1, v2) :
    if v1 > v2 :
        parents[v2] = v1
    else :
        parents[v1] = v2

union(v1, v2) (집합 합치기)

  • 목적: 두 정점 v1과 v2가 속한 집합을 합침.
  • 작동 원리:
    • v1과 v2의 크기에 따라 부모를 설정.
    • 작은 쪽이 큰 쪽의 자식이 됨. (여기선 번호가 작은 정점이 부모가 되는 규칙은 아님.)
  • 결과: 두 정점을 같은 집합으로 병합.
edges.sort()
sum_weight = 0

for w, v1, v2 in edges :
    v1_root = find(v1)
    v2_root = find(v2)

    if v1_root != v2_root :
        union(v1_root, v2_root)
        sum_weight += w

print(sum_weight)

간선 정렬:

  • 가중치 기준으로 오름차순 정렬.

최소 신장 트리 생성:

  • 간선들을 순회하면서, 두 정점이 서로 다른 집합에 속해 있다면 합침.
  • 가중치를 더하며 MST를 구성.

결과 출력:

  • MST의 총 가중치 출력.

이번주 문제는 새로운 알고리즘을 배워가는 문제였다. 어디서 본 기억은 나는데 제대로 공부한 적은 없는 알고리즘 이었다. 이번 기회에 다시 잘 정리하는 기회를 가졌으면 좋겠다.

반응형