공부
Union-Find, 크루스칼 알고리즘, 프로그래머스 문제풀이
1. Union FInd 관련 정리 노드와 간선이 연결되어 그래프가 주어질 때, 각 노드의 부모노드를 찾아 반환해주는 알고리즘 즉, 연결된 노드끼리 같은 그래프에 포함되어 있는지 확인하는 알고리즘 # 부모 노드 탐색 테이블에 위치한 값을 반환 def getgraph(graph, x): if graph[x] == x: return x else: return getgraph(graph, graph[x]) # 연결된 두 노드 중 부모 노드를 입력하는 함수 def uniongraph(graph, a, b): a = getgraph(graph, a) b = getgraph(graph, b) print(graph, a, b) if a < b: graph[b] = a else: graph[a] = b # 연결된 두 ..