[백준][C++] 19541 루머

BFS 연습문제로 풀게된 '루머' 문제이다.

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

19538번: 루머

복잡한 문제지만, 보자마자 BFS를 떠올리는 것은 어렵지 않았다.

BFS의 연습문제인 바이러스, 연구소 문제와 닮았다.

중간에 체크해야 하는 조건 하나가 추가되어서 귀찮은 것이 이 문제가 골드인 이유일 것이다.

 

내가 떠올린 아이디어는 러프하게 이 문제의 풀이과정을 그대로 따라가는 것이었다.

나는 파이썬에서 덱으로 BFS를 풀던 습관대로 덱을 사용하였다.

 

바이러스 문제처럼 보기 쉽게

"소문을 믿는 사람" == "감염된 사람"

이렇게 생각하도록 하자.

 

맨 처음 풀었을 때는 시간초과가 났다.

시간초과가 난 풀이과정은 다음과 같다.

 

0. 감염된 사람을 덱에 넣는다.

1. 감염된 사람을 덱에서 뺀다.

 

2. 감염된 사람과 인접한 사람에게 감염을 시도한다.

3. 인접한 사람이 감염이 되었는지 체크한다.

4. 감염이 되었다면 덱에 추가한다.

(2~4를 인접한 사람마다 반복,

이때 이전의 인접한 사람이 이후의 인접한 사람에게 영향을 주지 않도록 주의한다.)

 

5. 1에서 뺐던 사람이 모든 사람을 감염시키지 못했다면 다시 덱에 넣는다.

(1~5를 반복한다)

 

구현 코드는 다음과 같다.

// 틀린 이유로 자료형 사이즈도 고려 //
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector<int> dummy;
	vector< vector<int> > v; v.push_back(dummy); // 1부터 인덱스를 잡으려고 넣은 더미
	deque<int> d;
	
	int n; cin >> n;
	int time[n+1]; for (int i = 0; i < n+1; i++) time[i] = -1;

	//그래프 Input
	for (int i = 0; i < n; i++) {
		vector<int> p;
		while (true) {
			int person; cin >> person;
			if (person == 0) break;
			p.push_back(person);
		}
		v.push_back(p);
	}
    
    //최초 감염자 Input
	int first_n; cin >> first_n;
	while(first_n--) {
		int first_p; cin >> first_p;
		d.push_back(first_p);
		time[first_p] = 0;
	}
    
    //BFS//
	while (!d.empty()) {
		int person = d.front(); d.pop_front(); //감염원
		vector<int> near = v[person];
		vector<int>::iterator itr;
		bool isAll = true;
		for (itr = near.begin(); itr != near.end(); ++itr) { //인접한 사람에 대해 반복
			int now_tell = *itr;                             					
			if (time[now_tell] > -1) continue;	//인접한 사람이 이미 감염됐으면 패스			 					
			
			isAll = false;
			vector<int> check = v[now_tell];	//인접한 사람의 인접한 사람들 조사			 					
			vector<int>::iterator itr2; int cnt = 0;
			
			for (itr2 = check.begin(); itr2 != check.end(); ++itr2) {
				if (-1 < time[*itr2] && time[*itr2] <= time[person]) cnt++;		
			}
			
			if (cnt >= check.size()/(double)2) { // 인접한 사람 주변에 감염자가 절반이상이면 덱추가
				time[now_tell] = time[person] + 1;			 					
				d.push_back(now_tell);					     					
			}
		}
		
        if (!isAll) d.push_back(person); // 기존 감염원이 모든 사람을 전파시키지 못했다면 덱추가								
	}

	//answer print
	for (int i = 1; i<n+1; i++) cout << time[i] << ' ';
}

그래프의 저장은 당연히 인접리스트를 활용했다.

최대 20만의 데이터가 있으니 인접행렬을 썼다가는 메모리가 남아나질 않을 것이다.

 

벡터 원소에 접근할 때, 헷갈리지 않기 위해서 더미를 넣어 1부터 시작하도록 맞췄다.

덱에 원소를 넣고 뺼 때, 시간정보를 같이 넣고 뺼 수도 있겠지만,

그렇게 하면 변수 관리하기가 귀찮을 것 같아서 그냥 시간에 대한 배열을 만들어버렸다.

(time 배열)

각각의 사람들에 대해 최초로 감염된 시간을 저장하는 배열이다.

 

감염원에 대해 주변 감염된 사람을 한명씩 조사하여 덱에 넣는데,

이때 주의할 점은 이전 결과가 이후의 결과에 영향을 주지 않게 하는 것이다.

예제 입력 1에서

1번은 2번을 바로 감염시킨다. 2번의 주변사람이 1번과 3번으로 두명인데,

1번이 이미 감염되어 있기 떄문에 절반이 넘기 때문이다.

 

반면 1번은 3번을 바로 감염시키지 못한다.

3변의 주변사람이 1, 2, 4번으로 3명인데 1번만 감염되어있어

절반을 넘지 못하기 때문이다.

 

감염자를 한명씩 관리할 경우, 자칫하면

2번이 감염된 것으로 처리한 순간,

3번을 체크할 때 2번이 감염된 것을 같이 세어

3번이 2번과 같은 시간에 감염되었다고 체크할 수 있다.

 

그래서 나는 조건을 다음과같이 걸었다.

if ( -1 < time[*itr2] && time[*itr2] <= time[person] )

2번이 감염된 시간은 1번이 감염된 시간 + 1이다.

따라서 1번이 감염된 시간까지의 범위에서 주변인의 감염 여부를 조사하면

2번의 감염여부는 3번에게 영향을 주지 않는다.

 

마지막에 조건을 하나 더 주었는데

예제입력 1의 첫번째 시점으로 설명한다면

 

1번이 2, 3번 두명의 인접한 사람을 "모두" 감염시키지 못했을 때

1번은 다시 덱에 넣어 3번을 감염시키도록 재시도한다.

 

라는 의미의 코드이다.

이 코드를 넣은 이유는 사실 단순히 불안해서였다 ㅋㅋ

만약 1번의 결과로 2번과 3번을 모두 감염시키지 못했는데,

중간에 모종의 이유로 2번과 3번이 1번의 시도에 의해 감염이 가능한 상태가 된다면 어떻게 할까?

 

이런.. 이유였다ㅋㅋ

이 코드를 가지고도 충분히 예제입력에서는 답이 잘 나왔기 때문에

시간초과를 받고나서 다른 사람의 사례를 찾아가며 시간초과를 해결할 이유를 찾아보았다.

 

1. 나누기보다 곱하기를 해야 시간이 줄어들 것이다?

인접한 감염자 수가 총 인접한 사람 수의 절반을 넘을 경우 감염된다.

라는 조건을 맞추기 위해 (double)로 형변환까지 해가며 2로 나눴다.

이것보다 거꾸로 생각해서

인접한 감염자 수 * 2 >= 총 인접한 사람 수

이 조건으로 체크하면 어떨까 싶었다.

 

사실 사소하게는 시간개선이 되었을 것으로 생각하지만,

여전히 시간초과가 났었다.

 

2. 같은 시간대에서 한번 추가되었던 사람이 다시 추가되어 시간이 더 걸린다?

오 뭔가 그럴듯해 보이는 이유였다.

같은 시간대를 체크하는 코드와, 추가되었는지 확인하는 배열을 추가해보았다.

여전히 시간초과가 났다.

이 부분은 문제가 아니었다.

 

그러다가 문득 이 생각이 들었다.

아까 불안해서 넣었던 "그 코드"

필요한 걸까?

 

주석처리를 하니 맞았다.

바로 위에 적은 2번 조건을 지우고 제출하니 오히려 시간이 더 감소하며 빠르게 맞혔다.

 

1번이 2, 3번 두명의 인접한 사람을 "모두" 감염시키지 못했을 때

1번은 다시 덱에 넣어 3번을 감염시키도록 재시도한다.

 

여기에서 1번은 다시 검사할 필요가 없었다.

왜냐하면

1번 2번, 3번을 모두 감염시키지 못했을 때,

2번 3번은 그 시점에서 덱에 추가가 되지 못했으므로

1번은 의미가 없기 때문이다.

 

내가 걱정한 것은 1번하고 연결은 안되었지만

4번이 2번 3번의 감염여부에 영향을 주어 1번이 감염을 시도했을 때 성공할 수 있다면

어떻게 하는 것이 좋은지에 대한 것이었다.

 

이것도 고려할 필요가 없는 것이 4번이 2번과 3번의 감염 여부에 영향을 주었다면

적어두 2번과 3번 둘중 하나는 감염이 되어 덱에 들어갔다는 이야기다.

굳이 1번이 아니더라도 감염이 되어 덱에 들어간 아이가 충분히 영향력을 행사할 수 있다.

 

최종 정답코드는 다음과 같다.

// 틀린 이유로 자료형 사이즈도 고려 //
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector<int> dummy;
	vector< vector<int> > v; v.push_back(dummy);
	deque<int> d;
	
	int n; cin >> n;
	int time[n+1]; for (int i = 0; i < n+1; i++) time[i] = -1;

	for (int i = 0; i < n; i++) {
		vector<int> p;
		while (true) {
			int person; cin >> person;
			if (person == 0) break;
			p.push_back(person);
		}
		v.push_back(p);
	}
	int first_n; cin >> first_n;
	while(first_n--) {
		int first_p; cin >> first_p;
		d.push_back(first_p);
		time[first_p] = 0;
	}

	while (!d.empty()) {
		int person = d.front(); d.pop_front();
		vector<int> near = v[person];
		vector<int>::iterator itr;
        
		for (itr = near.begin(); itr != near.end(); ++itr) {
			int now_tell = *itr;                             					
			if (time[now_tell] > -1) continue;				 					
			
			vector<int> check = v[now_tell];				 					
			vector<int>::iterator itr2; int cnt = 0;
			
			for (itr2 = check.begin(); itr2 != check.end(); ++itr2) {
				if (-1 < time[*itr2] && time[*itr2] <= time[person]) cnt++;		
			}
			
			if (cnt >= check.size()/(double)2) {
				time[now_tell] = time[person] + 1;
				d.push_back(now_tell);
			}
		}
	}

	//answer print
	for (int i = 1; i<n+1; i++) cout << time[i] << ' ';
}