[C++] 백준 2606: 바이러스

문제

[C++] 백준 2606: 바이러스 SILVER 3
https://www.acmicpc.net/problem/2606

 

---

 

접근 방법

백준 2606번은 컴퓨터 바이러스 문제로,
1번 컴퓨터가 바이러스에 감염되었을 때 연결된 다른 컴퓨터가 몇 대 감염되는지 구하는 문제다.

 

컴퓨터들이 네트워크로 연결되어 있기 때문에, 이를 그래프 탐색 문제로 볼 수 있다.

문제의 핵심은 다음과 같다.

• 컴퓨터 = 노드
• 네트워크 연결 = 간선

따라서 그래프 탐색(DFS 또는 BFS) 을 이용해서 1번 컴퓨터에서 시작하여 연결된 모든 컴퓨터를 방문하면 된다.

 

이번 풀이에서는 DFS(Depth First Search) 를 사용했다.

먼저 그래프를 인접 리스트 형태로 저장한다.

vector<vector<int>> graph;

그리고 방문 여부를 확인하기 위해 배열을 사용했다.

vector<bool> visited;

 

DFS는 다음과 같이 구현했다.

void dfs(int node)
{
    visited[node] = true;

    for (int i = 0; i < graph[node].size(); i++)
    {
        int next = graph[node][i];

        if (!visited[next])
            dfs(next);
    }
}

1번 컴퓨터부터 DFS를 시작하면 같은 네트워크로 연결된 모든 컴퓨터가 방문된다.

마지막으로 1번 컴퓨터를 제외한 방문된 컴퓨터 수를 세면 감염된 컴퓨터 수가 된다.

구현 시 주의할 점

• 그래프는 양방향이다.
• 마지막 cnt에서 수를 갱신할 때 1번 컴퓨터는 제외하도록 2번 노드부터 for문을 돌린다.

 

---

 

코드

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

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node)
{
	visited[node] = true;
	for (int i = 0; i < graph[node].size(); i++)
	{
		int next = graph[node][i];
		if (!visited[next])
			dfs(next);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0, m = 0;
	cin >> n >> m;

	graph.resize(n + 1);
	visited.resize(n + 1, false);
	for (int i = 0; i < m; i++)
	{
		int a = 0, b = 0;
		cin >> a >> b;

		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	dfs(1);

	int cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		if (visited[i])
			cnt++;
	}
	cout << cnt;
}