[C++] 백준 온라인 저지 2606번 바이러스 풀이

서로 연결되어 있는 컴퓨터 중에서 바이러스에 감염된 컴퓨터가 몇 개인지 구하는 문제

 

---

문제의 조건

 

1. 컴퓨터의 갯수 N, 서로 연결된 쌍 M개가 주어진다. 

 

2. 1번 컴퓨터는 바이러스에 걸렸는데 이 바이러스는 네트워크를 통해서 전파된다. 

 

3. 1번 컴퓨터부터 시작해서 서로서로 연결되어 있는 컴퓨터들은 연결된 컴퓨터에게서 바이러스가 옮았다. 

 

4. N개의 컴퓨터 중에서 1번 컴퓨터를 빼고 몇 개의 컴퓨터가 바이러스에 걸렸는지 출력

 

---

풀이 과정

 

쉽게 생각하고 시작했는데 생각보다 오래 걸린 문제

ㅠ.ㅠ

아직 dfs/bfs가 완벽하지 않아서 그런가 봅니다. 

 

단순하게 모든 정점을 탐색하는 코드는 쉽게 짤 수 있지만 

조금만 응용되어 나오면 방문할 필요가 없는 정점을 어떻게 거르나 고민하면서 시간을 많이 썼습니다. 

 

 

풀이

1. 양방향 연결 그래프를 만든다. 

 

2. bfs로 연결된 정점들을 탐색한다. 

 

3. 서로 연결된 정점들의 갯수를 센다. 

 

---

 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> computers;
vector<bool> visited;
int bfs(int start)
{
    int answer = 0;
    queue<int> q;
    q.emplace(start);
    
    while (!q.empty())
    {
        int curVertex = q.front();
        q.pop();
        
        for (int i = 0; computers[curVertex].size() > i; i++)
        {
            //현재 정점과 연결된 컴퓨터 중 방문하지 않은 컴퓨터가 있으면 방문한다. 
            //감염된 컴퓨터 갯수 증가 
            int neighbor = computers[curVertex][i];
            if (!visited[neighbor])
            {
                q.emplace(neighbor);
                visited[neighbor] = true;
                answer++;
            }
        }
    }
    
    return answer;
}

int main(int argc, const char * argv[])
{
    int N, M;
    cin >> N >> M;
    
    computers.resize(N + 1);
    visited.assign(N + 1, false);
    
    //시작 정점과 도착 정점이 서로 연결된 양방향 그래프 구성 
    for (int i = 0; M > i; i++)
    {
        int from, to;
        cin >> from >> to;
        computers[from].push_back(to);
        computers[to].push_back(from);
    }
    
    //1번 컴퓨터는 항상 감염되어 있으니까 방문 표시하고 시작 
    visited[1] = true;
    int answer = bfs(1);
    
    cout << answer;
    
    return 0;
}