소근소근

BFS/DFS 분류에 있는 문제였지만, 분리집합으로 풀었다. 컴퓨터 두대가 연결 되면 같은 네트워크(같은 집합)으로 분류되기 때문이다. 연결된 컴퓨터 두대는 union해서 같은 집합으로 보고, 마지막에 집합의 개수를 출력하면 된다. #include #include #include #include #include using namespace std; int parent[200]; map m; int Find(int x){ if(x==parent[x]) return x; return parent[x] = Find(parent[x]); } void Union(int x, int y){ int px = Find(x); int py = Find(y); if(px != py){ parent[px] = py; } }..

백준 4195 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구 관계 정보를 받아 친구 네트워크에 속하는 친구 수를 출력하는 문제로, 분리 집합(disjoint set)을 이용하여 풀었다. 숫자가 아니라 문자열을 입력 받으므로 자료구조 map을 이용하여 로 저장하여 정수로 처리했다. union find 설명 글 https://steptoprogrammer.tistory.com/64 [알고리즘/자료구조] 분리 집합( ..

분리 집합이란 교집합이 존재하지 않는 두개 이상의 집합을 뜻한다. 구분해야 하는 데이터 집합들을 다루는 알고리즘에서 사용할 수 있다. 분리집합에서는 자식 노드가 부모 노드를 가리키게 되어 있다. 보통 특정 집합의 대표 노드(루트)를 자식 노드들이 가리키고 있는 형태이다. 분리집합 연산에는 두 가지가 있다. 1. Union(x,y) 합집합 연산이다. 두개의 집합을 합치기 위해서 각 두 집합의 대표(루트)노드를 찾고, A의 대표노드의 부모를 B의 대표 노드로 설정한다. void Union(int x, int y) { int px = Find(x); int py = Find(y); if (px != py) { parent[px] = py; set_size[py] += set_size[px]; } } 합치려고 ..