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

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

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

https://www.acmicpc.net/

문제

https://www.acmicpc.net/problem/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

기억해야할 것

유니온 파인드가 정의되어 있는 줄 몰랐다

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

from http://pythaac.tistory.com/198 by ccl(A) rewrite - 2021-08-24 06:26:52