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(..

1. 신장 트리 (Spanning Tree)신장 트리는 모든 노드끼리 연결되어 있는 (모든 노드 간에 경로가 존재하는) 연결 그래프가 주어졌을 때, 모든 노드가 연결되지만 사이클이 존재하지 않는 부분 그래프를 의미한다.그래프의 최소 연결 부분 그래프라고 할 수 있다.여기서 최소 연결이란, 간선의 수가 최소가 되는 부분 그래프를 의미한다.n개의 노드가 있을 때 간선의 수는 n-1이 된다.2. 최소 신장 트리최소 신장 트리는 연결 그래프가 주어졌을 때, 가능한 신장 트리 중 가중치 합이 가장 작은 트리이다.2.1. 최소 신장 트리의 특징간선의 가중치 합이 최소여야 한다.노드가 n 개일 때, 간선은 반드시 n-1 개다. (신장 트리 특징)사이클이 존재하지 않는다. (신장 트리 특징)3. 크루스칼 (Kruska..