반응형 union find2 BOJ 1717 : 집합의 표현 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1717 유니온 파인드를 이용하여 문제를 풀 수 있다. 각 원소들의 부모를 자기 자신으로 초기화하고 입력을 받으면서 집합을 만든다. find를 이용하여 같은 집합에 포함되어 있는지 체크하면 된다. #include int N, M; int parent[1000100]; int find(int x) { if (x == parent[x]) return x; return parent[x] = find(parent[x]); // 경로 압축 } void makeUnion(int x, int y) { x = find(x); y = find(y); if (x != y) parent[x] = y; } int main(void) { scan.. 2021. 6. 10. BOJ 2606 : 바이러스 (유니온 파인드 Union Find) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2606 유니온 파인드(Union Find)를 이용하면, 원소가 어떤 집합에 포함되어 있는지 알 수 있다. 유니온 파인드에서는 2가지 연산이 필요하다. find(x) : x가 포함된 집합을 찾는다. (root 원소를 찾는다.) makeUnion(x, y) : x와 y가 같은 집합에 포함되도록 합친다. parent[y] = x가 된다. 그리고 각 원소별로 자신의 부모를 저장할 parent 배열이 필요하다. 바이러스 문제는 그래프(링크드 리스트)를 만드는 기본 문제지만, 집합으로도 해결 가능하다. 이 문제에서는 1번 컴퓨터와 연결된 컴퓨터의 수를 찾아야 한다. Find( 2 ~ N ) 과 Find( 1 )의 집합이 같으면 1번.. 2021. 6. 8. 이전 1 다음 반응형
