어흥

문제 링크: https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 입력 첫째 줄에 www.acmicpc.net 1. 주의할 점 - MST에 대해 알고 있어야 한다 - Float값으로 받아들인 후, 소수점 이하 2번째 자리까지 반올..

문제 링크: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 www.acmicpc.net 1. 주의할 점 - MST의 알고리즘으로는 프림이나 크루스칼이 존재하는데 둘중 하나로 풀면 된다 - 간선의 개수 적으..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - A 지점부터 B지점까지(A!=B)의 거리를 저장하는 2차배열을 생성할 필요가 없다(Long 타입으로 최대 1000*1000 생성시 메모리 손해) - List를 이용해서 구현한다 - 소숫점 첫째자리에서 올림하는 경우는 최종단계에서만 1번 진행한다. - 그래프 내에 간선의 수가 적다면 Kruskal이, 간선이 많다면 Prim이 적절한 알고리즘이다 2. 구현 [Kruska..