[백준 1647] 도시 분할 계획 - cpp로 구현한 최소 신장 트리
문제 개요문제 번호: 1647제목: 도시 분할 계획난이도: 골드 4링크: 백준 1647번문제 설명N개의 집이 있는데 연결되어있는 도로를 없애 N개의 집들을 2개의 마을 집단으로 분할해야한다.접근 방법도로를 지우는 것이 아닌 주어지는 M개의 도로에서 비용이 적은 도로를 선택한다.이때 마을1과 마을2는 서로 도로가 연결 되어 있으면 안된다. 즉 처음에 N개의 집을 각각의 집합으로 지정하고 도로를 연결할때 마다 집합을 합하여 2개의 집합으로 만들면 된다.이때 사용되는 알고리즘은 Union-Find를 이용한 크루스칼 알고리즘을 이용한다. 구현 코드#include#include#includeusing namespace std;int n, m;tuple edge[1000005];int p[100005];int fi..
알고리즘
2024. 10. 17. 23:03