알고리즘 문제풀이[Algorithm]
[백준] 4386번 별자리 만들기(크루스칼 알고리즘)(Python - 파이썬)
문제 접근 n개의 별들의 좌표를 입력 받아서 그 별들을 이어 별자리를 만들 수 있는데 별자리를 만드는데 드는 최소 비용을 구해야합니다. 별자리의 조건은 다음과 같습니다. - 별자리를 이루는 선은 서로 다른 두별을 일직선으로 이은 형태이다. - 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별은 2차원 평면 위에 놓여있고 선을 하나 이을 때 마다 두 별 사이의 거리만큼의 비용이 든다고 합니다. 별자리의 조건 및 문제를 통하여 최소 신장 트리를 구해야한다는 것을 알 수 있습니다. 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구하였습니다. 2022.03.06 - [정보[Information]] - 신장 트리(Spanning Tree) / 크루스칼 알고리즘(Kruskal Algo..
2022. 3. 11. 16:40
최근댓글