블로그 이름 뭐로 하지

문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 최소 스패닝 트리를 조금 활용한 문제...? 라고 보면 될 것 같다. 프림 알고리즘을 이용해서 풀었고, 일반적으로 그래프 문제들은 연결돼있는 간선과 노드의 정보를 주는 경우가 많은데 얘는 그 정보를 두 점 사이의 거리를 활용해서 직접 만들어야 하는 문제였다. math.sqrt를 통해 제곱근을 구했고, 소수점 둘째자리까지만 활용하기 위해 round 함수를 사용했다. 이 외에는 일반적인 프림..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 트리 - 사이클이 존재하지 않는 그래프 스패닝(신장) 트리 - 그래프 내의 모든 노드를 포함하면서 사이클이 없는 부분 그래프 최소 신장 트리 - 그래프 내의 모든 노드를 포함하면서 사이클이 없는 부분 그래프 중 가중치의 합이 최소가 되는 신장 트리 최소 신장 트리를 구할 수 있는 알고리즘에는 프림, 크루스칼 알고리즘이 있다. 크루스칼과 프림..