[백준 2606] 바이러스(C++)

📕문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

📕입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

📕출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

---

💡문제해석

이 문제는 DFS, BFS 중 무엇을 사용하든 풀 수 있는 문제이다. 효율성 측면에서는 입력이 어떻게 주어지느냐에 따라 다르기 때문에 확정 지어서 말을 할 수는 없다.

나 같은 경우에는 둘 다 사용해도 상관없다면 DFS에서 재귀를 사용하는 편이다. [간단한 문제라면]

출발점이 1로 고정되어 있기 때문에 굉장히 쉽게 풀 수 있는 문제이다.

쉬운 문제이기 때문에 세세한 코드 설명은 안 하고 전체 코드를 올릴겅

---

📜코드

/*
백준 2606 실버1 바이러스
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, t, ans = 0;
vector<vector<int>> graph;
vector<int> visit;
void Dfs(int vir);
int main()
{
    cin >> n >> t;
    visit.resize(n + 1, 0);
    graph.resize(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < t; i++)
    {
        int s, f;
        cin >> s >> f;
        graph[s][f] = 1, graph[f][s] = 1;
    }
    visit[1] = 1;
    Dfs(1);
    cout << ans;
}
void Dfs(int vir) //무조건 1번 컴퓨터가 바이러스라고 가정함.
{
    for (int j = 0; j <= n; j++)
    {
        if (graph[vir][j] == 1 && visit[j] == 0)
        { // 0이 방문 안한 상태
            visit[j] = 1;
            ans++;
            Dfs(j);
        }
    }
}

✔느낀 점

• 그냥 쉬운 문제임 난이도 실버 3이라는 게 맞음.