최소비용으로 모든 노드를 연결(=최소신장트리)하기 위한 알고리즘
최소 신장 트리 : 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선 중 가중치 합이 최소가 되는 트리
최상위 부모노드를 저장하고 확인하기 위해 사용. 사이클 이루는지 판별.
def find(a): if parent[a] != a: parent[a] = find(parent[a]) return parent[a] def union(u,v): sp = min(find(parent[u]), find(parent[v])) bp = max(find(parent[u]), find(parent[v])) parent[bp] = sp
입력 : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
출력 : 4def solution(n, costs): answer =0 costs.sort(key = lambda x: x[2]) ## 1. 입력값 정렬 parents = [i for i in range(n+1)] for x in costs: # 각 입력에서 두 노드 순서를 정렬했다. -> union계산 필요없어짐 x[0], x[1] = min(x[0], x[1]), max(x[0], x[1]) def find(x): if parents[x] == x: return x else: parents[x] = find(parents[x]) return parents[x] def union(a,b): ## 위처럼 x[0],x[1]을 정렬한 경우 필요없다.. ! ap = find(a) bp = find(b) if ap!=bp : parents[bp] = ap for n1, n2, cost in costs: ## 2. 순서대로 최상위노드(부모)확인 ->find() if find(n1) != find(n2): ## 3. 부모 다른경우 두 최상위 부모중 작은값으로 갱신시키고 그래프에 추가 parents[find(n2)] = find(n1) # union(n1, n2) answer +=cost return answer
무방향 연결 그래프에서 몇개의 연결 집합이 생기는 지 계산
-> 가중치가 없다 ! = 정렬할 필요 없음def find(a): if parent[a] != a: parent[a] = find(parent[a]) return parent[a] def union(u,v): sp = min(find(parent[u]), find(parent[v])) bp = max(find(parent[u]), find(parent[v])) parent[bp] = sp ... # 연결 집합의 갯수!를 구하려면 !! ans = [] for i in range(1, n+1): ans.append(find(parent[i])) #parent배열값으로 find! print(len(set(ans))) #중복값 제거 후 카운트
문제 목록
boj10451순열사이클