8주차(최소신장트리) - [C++]백준2606 바이러스

06 May 2022 in Study on Algorithm

백준2606 바이러스 링크

문제

예제 입력

---

코드

#include<iostream>
using namespace std;

int arr[101];

// 원소가 속한 집합 찾기  
int find(int x) {
    if (arr[x] != x) arr[x] = find(arr[x]);
    return arr[x];
}

// 두 원소 집합 합치기  
void Union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a < b) arr[b] = a;
    else arr[a] = b;
}

int main() {
    int c, m;
    cin >> c >> m;

    for (int i = 1; i <= c; i++) arr[i] = i;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        Union(a, b);
    }

    // 컴퓨터에서 걸린 바이러스 수
    int ans = 0;
    for (int i = 2; i <= c; i++) {
        if (find(i) == find(1)) ans++;
    }
    cout << ans;
}

설명

이 문제는 서로소 집합의 개념을 사용하여 바이러스가 걸린 집합을 구하는 것입니다. 먼저 {1}{2}...{n}의 집합들을 배열로 표현하고 네트워크가 연결된 것을 같은 집합안에 있는 것으로 표현하여 Union()을 해줍니다. 그렇게 되면 바이러스의 시작점인 집합과 같은 집합인지 find()로 확인하여 카운트해주며 출력합니다.

---

결과