C++ 백준 2606 바이러스

백준 2606

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

2606번: 바이러스

풀이 전 나의 생각

컴퓨터 네트워크의 연결 구조가 그래프의 형태로 주어진다.

이때, 첫 번째 컴퓨터에 웜 바이러스가 퍼졌을 때 최대 몇 대의 컴퓨터 까지

퍼질 수 있는지 구해야 한다.

 

조건

- 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.

 

과정

웜 바이러스는 무조건 1부터 시작하고, 컴퓨터 1번과 연결된 컴퓨터들을 탐색하려면

그래프의 형태로 값을 저장해놔야 한다.

 

다음으로 DFS를 이용하여 각 컴퓨터를 탐색한다.

컴퓨터가 방문 조건을 만족하며 탐색 됐다는 의미는 웜 바이러스에 걸렸다는 의미기 때문에,

방문 표시를 해주며 최종 결과값을 증가시켜준다.

 

 

1. 컴퓨터 네트워크의 구조를 저장한다.

for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;

		link[u].push_back(v);
		link[v].push_back(u);
	}

 

2. DFS탐색으로 컴퓨터의 방문 표시를 해주며 웜 바이러스 현황을 체크해준다.

void dfs(int st)
{
	visted[st] = true;

	for (int next : link[st])
	{
		if (!visted[next])
		{
			dfs(next);
			ans++;
		}
	}
}

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>> link(101);
bool visted[101];
int ans = 0;

void dfs(int st)
{
	visted[st] = true;

	for (int next : link[st])
	{
		if (!visted[next])
		{
			dfs(next);
			ans++;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;

		link[u].push_back(v);
		link[v].push_back(u);
	}

	dfs(1);
	cout << ans;
}