Union Find (2) 썸네일형 리스트형 백준 1647 도시 분할 계획 : 전형적인 MST + 부모 동일 유무 파악시 주의할 점 문제 링크 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 풀이 아이디어 오랜만에 mst(minimum spanning tree) 문제를 풀어보았다. MST의 구현 방법의 기본은 union find 이므로 반드시 union find(disjoint set) --> MST 순서대로 공부할 것. 그러면 내가 코드에 쓴 find(),union() 함수의 의미를 알 것이다. 알 것이라 가정하고, 문제는 각 edge의 cost 값.. 백준 1976 여행가자 - 2차원 array 형태로 데이터 주어질 때 효과적인 union find 문제 링크 www.acmicpc.net/problem/1976 풀이 아이디어 2차원 배열에 메모리를 할당해서 0과 1을 전부 저장할 필요가 없다. 1이 나올 시에는 두 노드를 가지고 disjoint set을 만드는 것이므로, 바로 union find를 때려 버리면 되는 문제였다. 코드 #include using namespace std; int n,m; int node; int root[201]; int find(int x){ if(root[x]==x) return x; else return root[x]=find(root[x]); } void un(int x, int y){ x = find(x); y = find(y); root[x]=y; } int main(void){ cin>>n>>m; for(in.. 이전 1 다음