백준 2606번: 바이러스

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

2606번: 바이러스

 

이 문제는 BFS,DFS 또는 유니온 파인드로 풀 수있다. 그래서 두 가지 풀이로 풀것이다 BFS와 유니온파인드이다.

유니온 파인드로 풀 수있는 이유는 바이러스 감염여부이고 이 그래프가 어떤 노드가 어떤 노드를 연결하고 있고는 중요하지 않고 같은 그래프인지 아닌지만 파악하면 되기 때문이다. 그래서 유니온 파인드로 풀어봤다. 

그냥 간단하게 연결 된 쌍을 다 유니온 파인드 해버리면 결국 쌍이 이루어지는것들은 같은 루트노드를 가리키게 된다. 즉 같은 그래프 라는 것이다 . 코드를 보자

유니온 파인드 코드

#include <iostream>
#include <vector>
using namespace std;
int parent[101];
int find(int x){             //유니온 파인드
  if (x==parent[x]){
    return x;
  }
  else{
    int y = find(parent[x]);
    parent[x] = y;
    return y;
  }
}
void Union(int x,int y){
  x = find(x);
  y = find(y);
  parent[y] = x;
}
int main(){                      
    int n,m;
    int ans=0;
    cin >>n>>m;
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
    while(m--){                       //쌍을 이루는 것들을 같은 그래프로
        int x,y;
        cin>>x>>y;
        Union(x,y);
    } 
    for(int i=2;i<=n;i++){             //1과 같은그래프면 값추가
        if(find(1)==find(i)){
            ans++;
        }
    }
    cout<<ans;
}

 

BFS 코드 

메모리를 조금이라도 아끼려고 vector 값 사용

#include <iostream>
#include <vector>
using namespace std;
bool check[101];
int ans;
void dfs(vector<vector<int>>& v,int x){        //dfs 벡터
    ans++;
    check[x]=true;
    int len=v[x].size();
    for(int i=0;i<len;i++){
        if(check[v[x][i]]==false){         
            dfs(v,v[x][i]);
        }
    }
}
int main(){
    int n,m;
    cin >> n>>m;
    vector<vector<int>> v(n+1);
    while(m--){
        int x,y;
        cin >> x>>y;
        v[x].push_back(y);           //양방향 그래프이기 때문에 둘다 들어가기
        v[y].push_back(x);
    }
    dfs(v,1);
    cout <<ans-1;
}