[2606] 바이러스

1. 문제

www.acmicpc.net/problem/2606

2606번: 바이러스

 

2. 접근 방법

1) PC 간의 연결 정보를 나타내기 위해 2차원 벡터를 선언한다(v).

 

2) dfs의 방문 정보를 나타내기 위해 bool 타입의 벡터를 선언한다(visited).

 

3) PC간 연결 정보는 양방향이므로 v에 값을 넣을 때 이 점을 유의하여 a-b의 연결 정보를 v[a]와 v[b]에 각각 저장한다.

 

4) 재귀 함수인 dfs를 선언하여 감염된 PC개수인 cnt를 반환한다.

 

 

3. 실수했던 부분 & 처음 알았던 부분

1. 처음에 v에 pair<int,int>쌍으로 연결 정보를 저장하려 했음 -> 이렇게 하면 하나의 pc에 연결된 pc정보를 알기 위해서 모든 vector를 다 순환해야 한다.

=> 따라서 "2차원 벡터를 선언한 후, 하나의 PC에 연결된 pc 정보들을 하나의 벡터로 저장하게끔 한다."

 

2. dfs를 재귀함수로 돌리기 위해선 vector들을 전역으로 옮길 것

 

3. vector를 전역으로 옮기면 초기 사이즈(N,M)등을 모르기 때문에 1) MAX로 사이즈를 선언하거나 2) v.reserve(N+1)로 main함수 내에서 다시 사이즈를 조정한다. 

=> 엥간하면 MAX로 사이즈를 처음부터 정하자(초기값도 한번에 넣기 편하므로)

 

4. dfs 함수 내 'cnt = 1'은 현재 나도 감염이 되었다는 의미. 이렇게 cnt를 지역변수로 넣기 불편하면 아예 전역변수로 빼자.

 

4. 코드

#include<iostream>
#include<vector>
#define MAX 101
using namespace std;

int N,M;
vector< vector<int> >v(MAX);
vector<bool> visited(MAX,false);
	
int dfs(int num) {
	if(visited[num]) return 0;
	visited[num] = true;
	
	int cnt = 1; //내가 전염됨
	for( auto next : v[num])
	 	cnt += dfs(next);
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 
	cin >> N >> M; 
	
	for(int i=0;i<M;i++) {
	 	int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	cout<<dfs(1) -1 <<endl; //1번을 제외한 컴퓨터 개수
	return 0;
} 

 

5. 느낀점

약 2달만에 처음으로 알고리즘 문제를 풀었더니 기본적인 문제도 버벅거렸다.. 코딩은 많이 푸는 것 보다 꾸준히 푸는 것이 제일 중요하다는 것을 깨달았다.. 다시 1일 1포스팅 가즈아아아