[BOJ] 2606번 바이러스 - C++

문제

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

2606번: 바이러스

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

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

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

---

풀이

DFS 기본 문제

 

입력 값을 2차원 배열로 저장해준다.

이 때, 무방향 그래프이니 a와 b의 값을 입력 받았을 때, arr[a][b]와 arr[b][a] 둘 다 1로 저장해야 한다.

 

입력이 끝나면 문제에서 1번 컴퓨터를 통해 바이러스에 걸린 컴퓨터의 개수만 구하면 되므로 DFS를 1번 노드에서만 돌려준다

감염된 컴퓨터의 개수를 세는 cnt값은 1번 컴퓨터를 방문할 때를 포함하면 안되니 cnt의 초기값을 -1로 지정해줬다.

---

코드

#include <iostream>

const int MAX = 101;

using namespace std;

int arr[MAX][MAX];
bool visited[MAX];
int cnt = -1, n, num; //1을 방문했을 때의 값을 제외해줘야되니 -1에서 시작

void dfs(int x) {
	visited[x] = true;
	cnt++;
	for (int i = 1; i <= num; i++) {
		if (!visited[i] && arr[x][i]) { //i값에 대해 방문한 적이 없고, 경로가 있는 상태면 dfs
			dfs(i);
		}
	}
}

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

	cin >> num >> n;

	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
        	//무방향 그래프 입력
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
    
	dfs(1); // 1로부터 감염되는 컴퓨터만 찾으면 되니 1에서부터만 탐색
    
	cout << cnt;
	return 0;
}

---

삽질 & 개선점

완전 어이없는 실수..

어차피 배열을 MAX로 지정해둬서 컴퓨터의 개수는 필요없겠지 하고 두 값을 모두 n으로 받아버리는 멍청한 실수를 해버렸다

그러다 보니 DFS를 돌릴 때 노드의 개수가 아닌 입력받은 간선의 개수만큼 돌아가다 보니 Out of Bounds가 되어버렸다ㅠㅠㅠ

꼭 값 받을 때는 주의하고 어떤 용도로 쓰는지 잘 체크하자!