백준 2606 바이러스(c++)

https://www.acmicpc.net/problem/2606

2606번: 바이러스

이 문제는 DFS, Union Find 등 다양한 알고리즘을 통해 해결할 수 있는 문제입니다. 저는 Union Find로 풀었는데, 이 자료구조를 통해 어떻게 해결했는지 설명드리겠습니다.

 

Union Find란 ?

 

상호 배타적 집합(Disjoint-set)들의 부분 집합들로 나눠진 원소들에 대한 자료구조

 

2가지 연산으로 이루어져 있다.

 

Find : x가 어떤 집합에 포함되어 있는지 찾는 연산(루트를 찾는 연산)

 

Find(x)는 x의 루트를 확인하는 연산입니다.

 

Union : x와 y가 포함되어 있는 집합을 합치는 연산

 

Union(x, y)는 y를 x로 붙이는 연산입니다. 

 

구현은 트리를 이용함. parent[i] = i의 parent가 저장되어 있음

 

Union(1,2), Union(4,5)의 연산 결과 값

하지만 이런 식으로 지속적으로 Union Find를 사용하게 된다면, 최악의 경우 O(N(노드의 개수))의 시간 복잡도가 발생하게 됩니다. 그래서 이를 방지하기 위해서 다음과 같이 재귀적으로 다시 루트를 찾는 방향으로 코드를 설계한다면, 최종적인 루트노드만 반환되게 됩니다.

parent[x] = y로 인해 루트 노드 1만 반환

<코드>

#include <iostream>

using namespace std;
int parent[101];
int Find(int x)
{
    if (x == parent[x])
        return x;
    else
        return parent[x] = Find(parent[x]);
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if (x != y)
        parent[y] = x;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        Union(x, y);
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        if (Find(1) == Find(i))
            ans += 1;
        // 1번 루트와 같으면 값 1 증가
    }
    cout << ans;
}

Union Find는 트리 구조이기 때문에, 각 배열의 요소마다 인덱스 값이 저장되어 있습니다. 그리고 입력받을 때마다 y의 parent를 x로 설정해 줍니다. 그리고 Find(1)(루트 노드)의 값을 비교하여 개수를 증가시켜 주는 방식으로 풀 수 있습니다.