그래프 알고리즘

1. 서로소 집합

• union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

2. 신장트리

• 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
• 크루스칼 알고리즘 (최소 신장 트리 알고리즘, 그리디)

3. 위상 정렬 알고리즘

• 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

백준 1647번

🔗 문제 링크

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

➕ 문제 해설

import sys
input = sys.stdin.readline

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())

parent = [0] * (N + 1)

for i in range(1, N + 1):
    parent[i] = i

edges = []
result = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append((C, A, B))

edges.sort()
# 유지 비용이 가장 큰 경로 없애서 마을 분리 
last = 0

for edge in edges:
    C, A, B = edge
    if find_parent(parent, A) != find_parent(parent, B):
        union_parent(parent, A, B)
        result += C
        last = C

print(result - last)

우선 크루스칼 알고리즘을 통해 최소 신장 트리를 만들었다. 2개의 마을로 분리하고, 유지 비용을 최소로 하기 위해서 마을의 길 중에 유지 비용이 가장 큰 길을 없앤다. 유지비용의 합을 나타내는 result에 정렬된 비용의 마지막 값을 빼서 위 조건을 만족하는 최소 유지비의 합을 구한다.

📝 정리

노드를 연결하는 간선을 최소한으로 가지고 있고 사이클이 존재하지 않게 하려면 크루스칼 알고리즘을 이용해야 한다.
입력 값이 많고 문제 풀때 시간 초과가 나면 import sys / input = sys.std.readline 을 사용하자.