CodeAngie

문제두 별 사이의 거리만큼 별자리를 만는 비용이 든다고 할 때,n개의 별들을 이어 별자리를 만드는 최소 비용을 구하는 문제이다.별자리의 조건두 별 사이의 거리는 서로 다른 두 별을 일직선으로 이은 선의 길이와 같다.모든 별은 직/간접적으로 연결되어 있다.풀이두 별 사이의 거리를 가중치로 두고, 크루스칼 알고리즘을 이용하여 최소 비용을 구한다.직각 삼각형의 대각선의 길이를 구하는 공식을 이용하여 가중치를 구한다.$c^2 = a^2 + b^2 $ $c = \sqrt{{a}^2 + {b}^2}$ $c = \sqrt{(x1-x2)^2 + (y1-y2)^2}$가중치와 두 별의 번호를 간선 list 에 저장한다.가중치를 기준으로 오름차순으로 간선 list를 정렬한다.작은 가중치부터 순서대로 별들을 연결한다. (부모..

문제그래프가 주어졌을 때 최소 스패닝 트리(최소 신장 트리)를 구하고 그의 가중치를 출력하는 문제이다.풀이크루스칼 알고리즘을 사용하여 가중치를 계산한다.간선(edge)을 가중치가 작은 순으로 정렬한다.부모 노드를 자기 자신으로 초기화한다.가장 작은 가중치부터 순서대로 노드를 서로 연결한다.노드를 서로 연결한다는 것은 두 노드가 같은 루트를 갖게 한다는 의미이다.즉 부모 노드가 다를 경우, 아직 서로 연결이 안 된 노드이기에union을 통해 부모 노드를 동일하게 만들어 줌으로써 서로 연결하는 것이다.Python 코드import syssys.setrecursionlimit(10**6)input = sys.stdin.readlinev,e = map(int,input().split())edges = [list(..