[백준][그래프] 최소 스패닝 트리

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

1197번: 최소 스패닝 트리

 

내가 작성한 코드

import sys, heapq
read = sys.stdin.readline

V, E = map(int, read().rstrip().split())
q = []
for _ in range(E):
    A, B, C = map(int, read().rstrip().split())
    heapq.heappush(q, (C, A-1, B-1))

group = [i for i in range(V)]
answer = 0

def group_update(A, B):
    global group
    if group[A] != A:
        is_same, group[A] = group_update(group[A], B)
        return (is_same, group[A])
    elif group[B] != B:
        is_same, group[B] = group_update(A, group[B])
        return (is_same, group[B])
    elif A == B :
        return (True, A)
    else:
        group[max(A, B)] = min(A, B)
        return (False, min(A, B))

for _ in range(E):
    C, A, B = heapq.heappop(q)
    is_same, grp = group_update(A, B)
    if not is_same:
        answer += C

print(answer)

• 크루스칼 알고리즘
  
  • 가중치가 작은 간선부터 선택하여, 모든 노드가 연결될 때까지 진행
  • 싸이클은 생성하지 않음
• 유니온 파인드
  • 집합을 나누고 합치는 방식이 유니온 파인드라는 이름으로 정의되어있음
  • 집합이 합쳐지면 모든 노드에 루트를 업데이트해줘야함

 

다른 사람이 작성한 코드

from sys import stdin

read = stdin.readline
V, S = map(int, read().split())

edge = []
for _ in range(S):
    a, b, w = map(int, read().split())
    edge.append((w, a, b))

edge.sort(key=lambda x: x[0])

parent = list(range(V + 1))


def union(a, b):
    a = find(a)
    b = find(b)

    if b < a:
        parent[a] = b
    else:
        parent[b] = a


def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])  # 경로 압축
    return parent[a]


sum = 0
for w, s, e in edge:
    if find(s) != find(e):
        union(s, e)
        sum += w

print(sum)

• union
  • 두 루트를 find로 찾아, 큰 값의 루트를 낮은 값으로 업데이트
• find
  • 루트면 반환
  • 루트가 아니면 재귀로 업데이트 후 반환

https://velog.io/@coding_egg/%EB%B0%B1%EC%A4%80-1197%EB%B2%88-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 1197번 : 최소 스패닝 트리 (python 파이썬)

 

기억해야할 것

• 유니온 파인드가 정의되어 있는 줄 몰랐다
  
  • 트리 문제 등에서 집합을 합치는 알고리즘을 가끔 사용 했었다
  • 사용하면서도 유니온 파인드라는 이름으로 정의되어 있는 줄 몰랐다
  • 이제 위 코드에서 배운 방식대로 사용해야겠다