[백준]2606 바이러스 C++ 문제 풀이

문제

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

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

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

입력

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

출력

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

예제 입력 1

7

6

1 2

2 3

1 5

5 2

5 6

4 7

예제 출력 1

4

---

그래프 탐색을 이용해 문제를 해결한다. 

 

먼저 각각의 컴퓨터를 노드라고 생각하고 연결 리스트를 만들어 본다. 

이렇게 (사진이 흐리네요>.<)

각 노드가 다음 함수를 거치면

이렇게 answer에 들어가게 된다.

문제 해결 방식

즉 answer이라는 배열은 감염되는 컴퓨터의 리스트를 넣은 것이고, 1번 컴퓨터를 제일 먼저 넣고 1번 컴퓨터와 연결되어 있는 컴퓨터들을 answer에 넣는다. 그 다음 배열 안에서 루프를 돌면서 똑같은 함수를 지속적으로 실행해 연결되어있는 컴퓨터가 answer에 없으면 추가하는 방식으로 진행한다. 그리고 answer에 있는 루프를 다돌았고, 더 이상 추가할 노드가 없는 경우에 실행을 종료한다. 

 

코드로 구현하자!

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector<vector<int>> list;
vector<bool> visit;
int answer = 0;

void dfs(int x)
{
	answer++;
	visit[x] = true;

	for (int i = 0;i < int(list[x].size()); i++)
	{
		if (!visit[list[x][i]])
			dfs(list[x][i]);
	}
}

int main()
{
	int computers; cin >> computers;
	int connect; cin >> connect; //연결된 컴퓨터 쌍의 개수
	int a, b;

	visit.resize(computers + 1);
	list.resize(computers + 1); //list의 사이즈 8로 지정
	for (int i = 0; i < connect; i++)
	{
		cin >> a >> b;
		list[a].push_back(b); // 벡터의 a번째 위치에 원소 b를 넣는다. 
		list[b].push_back(a);
	}
	// 이중 벡터에 연결리스트가 생성되었다.

	dfs(1);
	cout << answer - 1;
	return 0;
}