[백준 2606] 바이러스

 

1. 문제

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

2606번: 바이러스

 

2. 해결 IDEA

Union-Find 알고리즘 (초기상태)

Parent  Index	1	2	3	4	5	6	7	8	9
Node Index	1	2	3	4	5	6	7	8	9

 

바이러스 근원 노드가 '1'이므로 

1과 같은 Group으로 Union 되는 노드의 Parent Index가 '1'이 되도록하여

GetParent가 1인 노드의 갯수를 구함.

 

3. 소스코드

    #include <iostream>
    using namespace std;
    
    // 초기화 함수
    void initParent(int nodeNum, int parent[])
    {    
        for(int i = 1; i <= nodeNum; i++)
        {
            parent[i] = i;
        }
    } 
    // 부모 노드 찾는 함수
    int getParent(int i, int parent[])
    {
        if(i == parent[i])
        return parent[i];
        else
        return parent[i] = getParent(parent[i], parent);
     } 
     
    // 노드간 서로 같은 집합인지 체크하는 함수
    bool unionCheck(int a, int b, int parent[])
    {
        a = getParent(a, parent);
        b = getParent(b, parent);
        
        if(a == b)
        return true;
        else
        return false;
     } 
    
    // 노드를 서로 결합하는 함수
    void unionConnect(int a, int b, int parent[]) 
    {
        a = getParent(a, parent);
        b = getParent(b, parent);
        if(a < b)
        parent[b] = parent[a];
        else
        parent[a] = parent[b];
    }
 
int main(void)
{
    int ComputerNumber, EdgeNumber, VirusComputerNumber = 0;
    cin >> ComputerNumber;
    cin >> EdgeNumber;
    int Group[ComputerNumber+1];
    int start, end;
    initParent(ComputerNumber, Group);
    
    for(int i = 1; i<= EdgeNumber; i++)
    {
        cin >> start >> end;
        unionConnect(start, end, Group);
    }
    
    for(int i = 1; i <= ComputerNumber; i++)
    {
        if(getParent(i,Group) == 1) //부모노드가 1이라면 (바이러스 걸렸다면) 
        VirusComputerNumber++;
    }
    cout << VirusComputerNumber-1 << '\n';
    return 0; 
}