[백준/최소 스패닝 트리] 1197번. 최소 스패닝 트리, 1922번 네트워크 연결(Python)

문제

https://www.acmicpc.net/problem/1197

https://www.acmicpc.net/problem/1922

 

풀이

최소 스패닝 트리(Minimum Spanning Tree)

: 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

MST를 구하는 방법은 크루스칼 알고리즘과 프림알고리즘이 있다.

 

크루스칼 알고리즘 : 모든 간선에 대해 가장 가중치가 작은 간선부터 하나씩 이어나가며 모든 정점을 방문하는 방법

- 사이클이 발생하면 그 간선은 건너 뛰어야 한다.

- 사이클 발생유무를 체크하기 위해서는 유니온 파인드 구조를 사용한다.

- 간선이 연결하는 두 개의 노드가 같은 집합에 속하면? 사이클이 존재

- 간선이 연결하는 두 개의 노드가 같은 집합에 속하지 않는다면? 두 간선을 연결(union)하고 총 가중치에 현재 간선의 가중치 합산

- 시간 복잡도는 O(ElogE)이다.

 

프림 알고리즘 : 정점을 기준으로 인접한 간선들 중 가중치가 가장 작은 간선의 정점으로 이동하는 방법

- PQ를 이용해 구현한다.

- BFS와 유사하다.

 

다음은 유니온파인드로 푼 최소스패닝트리 코드이다.

두 문제는 풀이가 똑같았다!

# -*- coding: utf8 -*-
import heapq
from sys import stdin


def getParent(parent, x):
    # 부모노드를 찾는 함수
    if parent[x] == x:
        return x
    parent[x] = getParent(parent, parent[x])
    return parent[x]


def unionParent(parent, a, b):
    # 두 부모노드를 합치는 함수
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def findParent(parent, a, b):
    # 같은 부모를 가지는지 확인
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a == b:
        return 1
    return 0


def solution(V, E):
    # 자기 자신을 부모로 설정
    parent = [i for i in range(V+1)]
    edges = []
    sum = 0

    for _ in range(E):
        a, b, cost = map(int, stdin.readline().rstrip().split(' '))
        edges.append([cost, a, b])

    edges.sort(key=lambda x: x[0])  # 가중치가 작은 순서대로 정렬

    for cost, a, b in edges:
        if not findParent(parent, a, b):  # 부모가 다르다는 것은 사이클이 생기지 않는다는 것을 의미
            unionParent(parent, a, b)
            sum += cost
        # 부모가 같으면 가중치가 작더라도 pass
    return sum


V, E = map(int, stdin.readline().rstrip().split(' '))
print(solution(V, E))