Gidhub BE Developer

# [BOJ] 2606. 바이러스

2018-10-01
goodGid

## Problem

Problem URL : 바이러스

## [1] Answer Code (18. 10. 01)

``````#include <iostream>
using namespace std;

int n,m;
int arr[1005][1005];
int cash[1005];
int cnt;

void dfs(int v){
cash[v] = 1;
for(int i=1; i<=n; i++){
if( cash[i] != 1 && arr[v][i] == 1){
cnt ++;
dfs(i);
}
}
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

cin >> n >> m;

while (m--) {
int a,b;
cin >> a >> b;
arr[a][b] = arr[b][a] = 1;
}
cnt = 0;
dfs(1);

cout << cnt << endl;

return 0;
}
``````

### Review

• DFS를 통한 문제 해결

## [2] Answer Code (18. 10. 01)

``````#include<iostream>
using namespace std;
int p[105];

int Find(int x){
if(x == p[x])
return x;
else{
int y = Find(p[x]);
p[x] = y;
return p[x];
}
return x;
}

void Union(int x, int y){
x = Find(x);
y = Find(y);
p[y] = x;
}

int main(){
for(int i=1; i<=105; i++)
p[i] = i;

int n,m;
cin >> n >> m;

int a, b;
while (m--) {
scanf("%d%d", &a, &b);
Union(a, b);
}

int ans=0;
for(int i=1; i<=n; i++)
if( Find(1) == Find(i) )
ans ++;

cout << ans-1 << endl;
return 0;
}
``````

### Review

• Union & Find 알고리즘으로 문제 풀이.