목록별자리만들기 (1)

블로그 이름 뭐로 하지

[알고리즘/파이썬] 백준 4386 - 별자리 만들기

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