[Algorithm]Baekjoon 2606번 :: 바이러스

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

2606번: 바이러스

int parents[103] = { 0 };
 
int Find(int n)
{
    if (parents[n] == n) return n;
    return parents[n] = Find(parents[n]);
}
 
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a <= b) parents[b] = a;
    else parents[a] = b;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 1; i <= 102; i++)
    {
        parents[i] = i;
    }
 
    int vertexCount = 0;
    int edgeCount = 0;
    int a, b;
 
    cin >> vertexCount >> edgeCount;
 
    for (int i = 0; i < edgeCount; i++)
    {
        cin >> a >> b;
        Union(a, b);
    }
 
    int count = 0;
 
    for (int i = 2; i <= vertexCount; i++)
    {
        if (Find(i) == Find(1)) ++count;
    }
 
    cout << count;
}

이제 거의 탐색이나 그래프에서 기본예제같은 문제는 풀어도 따로 올리진 않는데, Union-Find에서 내가 실수했던게 있어서 안까먹으려고 올린다.

이 문제는 DFS나 BFS로 탐색해서 풀어도 되고 Union-Find로 풀어도 된다. 

1번집합의 개수를 구하는 문제이기 때문에 그런건데, 마지막에 1번컴퓨터와 연결된 컴퓨터의 개수를 구할 때 그냥 막연히 parents배열에서 값이 1인것만 찾아서 ++count 했더니 통과하지 못했다.

 

테스트케이스는 통과하기도 했고, Union과정에서 막연히 전부 다 제대로 업데이트 된거 아닌가 싶어서 다른사람 코드를 봤더니 Find(i) == Find(1) 이렇게 해놨길래 다시 생각해보니, 입력이 들어올 때 정점번호의 오름차순으로 들어오는게 아니라 랜덤으로 들어오기 때문에 모든 정점에 대해서 부모가 1로 전부 업데이트가 안되어있을 수 있다는걸 깨달았다.

같은 집합으로 표현되어있는거는 맞으나, 그 집합에서의 모든정점의 parent값이 최상위정점으로 업데이트가 안되어있다는것이다. 

MST의 가중치합을 구하려는 문제에서는 가중치만 구하면되기 때문에 굳이 전부 업데이트 안해도 됐었기 때문에 범한 실수였다.

실제로 기존에 실패했던 코드( if(parents[i] == 1) ++count )    를 하기전에 각 정점에 대해 Find(i)를 해서 최상위정점으로 업데이트시켜줬더니 정상적으로 통과가 됐다. 

지금이라도 실수를 알아서 정말로 다행이다.