바이러스

• 핵심
  : DFS / BFS 모두 풀리는 문제지만 그래프의 양방향성을 생각하는 것이 중요
• 반례

3
2
1 2
3 2 

일 경우에 단방향으로만 검사하면 3은 감염되지 않았다고 체크된다

코드

[ DFS - stack ]

#include <iostream>
#include <vector>
#include <stack>
using namespace std; 
bool vis[101];
vector<int> v[101];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T,N;
    cin >> T; // 컴퓨터의 수
    cin >> N; // 직접 연결되어 있는 컴퓨터 쌍의 수

    for(int i=0;i<N;i++)
    {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a); // 양방향 그래프이기 때문!
    }
    stack<int> s;
    s.push(1);
    vis[1] = true;
    while(!s.empty())
    {
        int cur = s.top(); s.pop();
        for(int idx=0;idx<v[cur].size();idx++)
        {
            if(vis[v[cur][idx]]) continue;
            vis[v[cur][idx]] = true;
            s.push(v[cur][idx]);
        }
    }
    int ans = 0;
    for(int i=2;i<=T;i++)
        if(vis[i]) ans++;
    cout << ans;
    return 0;
}

---

[ DFS - 재귀 ]

#include <iostream>
#include <vector>
#include <stack>
// 11:25 ~
using namespace std; 
bool vis[101];
vector<int> v[101];
int ans=0;
void DFS(int n){
    if(!vis[n]){
        ans++;
        vis[n] = true;
    }
    for(int idx=0;idx<v[n].size();idx++)
    {
        if(vis[v[n][idx]]) continue;
        else DFS(v[n][idx]);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T,N;
    cin >> T; // 컴퓨터의 수
    cin >> N; // 직접 연결되어 있는 컴퓨터 쌍의 수

    for(int i=0;i<N;i++)
    {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a); // 양방향 그래프이기 때문!
    }
    vis[1] = true;
    DFS(1);
    cout << ans;
    return 0;
}