[백준/C++] 2606번 : 바이러스 (DFS/BFS 연습)

바이러스

문제

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

예를 들어 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

---

DFS, BFS를 이용해 풀이하는 그래프 문제는 풀때마다 헷갈리는 것 같아 다시 연습해보았다.

 

먼저, 문제를 읽고 BFS를 이용하여 풀이해야겠다고 생각했다.

BFS를 이용한 풀이방법은 큐(Queue)를 활용하는 것이다. 

💡 BFS

#include <iostream>
#include <string>
#include <queue>

#define MAX 101

using namespace std;

int N, CompN;
int graph[MAX][MAX];
bool visit[MAX];

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

	cin >> N >> CompN;
	for(int i = 0; i < CompN; i++)
	{
		int pos, next;
		cin >> pos >> next;
		graph[pos][next] = graph[next][pos] = 1;
	}

	queue<int> que;
	que.push(1);
	visit[1] = true;
	int count = 0;
	while(!que.empty())
	{
		int pos = que.front();
		que.pop();

		for(int i = 1; i <= N; i++)
		{
			if(!visit[i] && graph[pos][i] == 1)
			{
				que.push(i);
				visit[i] = true;
				count++;
			}
		}
	}

	cout << count;
	return 0;
}

 

현재 그래프 노드와 다음 위치를 저장할 수 있도록 2차원 배열 graph를 선언하였고,

해당 문제에서는 방향그래프가 아닌 무방향 그래프이기 때문에 [현재노드][다음노드] 와, [다음노드][현재노드] 값을 모두 1로 변경하여 노드가 존재한다고 초기화하였다.

 

BFS 탐색인 만큼, 첫번째 컴퓨터인 1번 컴퓨터를 큐에 넣어준 뒤, 큐가 빌 때까지 while문을 수행하였다.

하나하나의 노드를 검색할 때 방문 여부(visit)를 판단하고, graph[큐에서 꺼낸노드][다음노드] 의 값이 1인지를 검사한다.

이때 현재 컴퓨터(노드)가 다른 컴퓨터(노드)들과 연결되어있는지 모두 비교해야 하므로 1부터 컴퓨터의 개수 N까지의 for문을 수행하였다.

 

BFS로 문제를 다 풀이하고 나서 DFS 탐색으로도 문제를 풀어보았다.

💡 DFS

#include <iostream>
#include <string>

#define MAX 101

using namespace std;

int N, CompN;
int graph[MAX][MAX];
bool visit[MAX];
int cnt = 0;

void DFS(int node)
{
	visit[node] = true;
	cnt++;

	for(int i = 1; i <= N; i++)
	{
		if (!visit[i] && graph[node][i])
			DFS(i);
	}
}

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

	cin >> N >> CompN;
	for (int i = 0; i < CompN; i++)
	{
		int pos, next;
		cin >> pos >> next;
		graph[pos][next] = graph[next][pos] = 1;
	}

	DFS(1);
	cout << cnt-1;
	return 0;
}

 

DFS 탐색은 보통 스택이나 재귀를 이용해 풀이하는데, 나는 재귀함수를 통해 풀어보았다.

 

BFS 탐색으로 풀이하는 방식과 거의 동일하지만, DFS 탐색에서는 큐를 사용하지 않고, 연결된 컴퓨터가 있다면 해당 컴퓨터로 DFS를 다시 실행하는 재귀함수를 이용하였다.

 

재귀함수를 통해 연결된 다음 컴퓨터 노드는 다시 현재 컴퓨터 노드가 되어, 또 자신에게 연결된 다음 컴퓨터 노드를 찾아간다.

---

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

2606번: 바이러스