[백준/2606] 바이러스

1. 문제

문제 링크 : www.acmicpc.net/problem/2606

2606번: 바이러스

컴퓨터 간의 연결 정보가 주어지고 바이러스에 감염된 컴퓨터와 연결된 컴퓨터들이 감염된다.

1번 컴퓨터에 의해서 감염되는 컴퓨터의 개수를 구하는 문제.

 

2. 풀이

전형적인 DFS, BFS 문제(저는 DFS로 풀어봤습니다).

dfs 함수는 자기 자신을 포함해서 자기 자신으로부터 감염되는 컴퓨터들의 개수를 리턴합니다.

연결된 컴퓨터를 방문할 때 방문한 적이 있다면 그 컴퓨터는 이미 감염된 컴퓨터이므로 0을 리턴해줍니다.

ex) (2, 3), (2, 4), (2, 7) 연결쌍이 있고 어느 컴퓨터도 방문한 적이 없다면 다면 2, 3, 4, 7 총 4를 리턴

다만 1번 컴퓨터에 의해서 감염되는 컴퓨터의 개수를 구하는 것이므로 최종 결과값에서 1번 컴퓨터를 빼줘야 합니다.

 

 

3. 코드

 

/*
	바이러스
	DFS
	난이도
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<vector<int>> links; // 컴퓨터 간 연결 정보
vector<bool> visited; // 방문 확인

int dfs(int cur){
	if(visited[cur])
		return 0;
	visited[cur] = true;
	int cnt = 1; // 자신이 감염되므로 1부터 시작한다.
	for(auto next : links[cur])
		cnt += dfs(next);
	return cnt;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;

	links.reserve(N+1);
	visited.reserve(N+1);

	fill(visited.begin(), visited.end(), false);
	
	for(int i=0;i<M;i++){
		int a, b;
		cin >> a >> b;
		links[a].push_back(b);
		links[b].push_back(a);
	}

	cout << dfs(1) - 1 << endl; // 1번 노드 제외

	return 0;
}

 

4. 느낀점

1) 블로그 개설하고 처음 올리는 거라 포맷 등 포스팅에 부족함을 많이 느꼈다.

2) 코드의 길이와 가시성 사이에 고민하다보니 코드가 이도저도 아니게 되는 것 같다.(전역변수 사용 + reserve 사용, answer 미사용 등)