[기출 상] 백준 19538 루머

[문제]

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

19538번: 루머

[풀이]

bfs를 이용하는 문제이다.

이전에 풀었던 토마토 문제와 비슷해서 bfs를 이용해야겠구나!라는 생각은 들었는데,,, 이 문제의 관점은 주변인들의 절반 이상이 루머를 믿을 때(감염되었을 때) 본인도 루머를 믿는다는 것이다. 먼저 bfs를 이용하므로 최초유포자인 사람들의 index를 큐에 넣고 그들의 시간을 0분으로 저장해준다. 큐에서 나온 유포자(감염자) 주변인들의 주변인들 절반이 감염되었다면 그들 역시 큐에 넣고 그들의 시간을 유표자의 시간 + 1로 갱신해준다.

그렇다면 주변인들의 절반이 감염되었는지는 어떻게 판단해야 할까? (주변인들의 수 / 2) 만큼을 저장해주고(turn) 감염자의 주변인으로 포함될 때마다 1씩 감소시켜주면 된다. 주변인들의 절반 이상이 감염되었다면 저장된 값이 0이하가 될 것이다. 3명이면 3/2+1인 2명이, 5명이면 5/2+1인 3명이 감염되어야 한다. 이때 주변인들을 저장하는 배열에 0까지 포함시켜 저장했으므로 +1은 안해주어도 된다. 

여기서 한가지 더 고려해주어야 할 것은, 감염자가 중복으로 판단되는 경우가 있으면 안된다는 것이다. 예를 들어, 1번 감염자의 주변인인 2번은 절반 이상이 감염되어 감염되었다. 그런데 마찬가지로 1번 감염자의 주변인인 3번은 절반 이상이 안되어 감염되지 않았다고 하자. 이 상황에서 1번 감염자를 다시 중복해서 탐색하게 되면, 3번의 입장에서는 사실상 1번 감염자 1명만 감염이 된 것임을 인지하지 못하고 주변인 2명이 감염이 된 것으로 생각할 수 있다. 만약 2명이 3번의 주변인의 절반이상인 숫자라면, 3번을 감염자로 잘못 판단하고 큐에 넣을 수도 있는 것이다. 따라서 큐에 넣을 때는 이 사람이 새롭게 감염되는 사람인지를 판단하기 위해 answer 배열을 -1로 초기화 하고 확인하도록 한다.  

 

[코드]

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> solution(int n, vector<vector<int>> surround, vector<int> firstInfected) {
	
	queue<int> q;
	vector<int> turn(n + 1); // 주변인의 절반이상이 감염되어야 함. 감염 조건을 만족하기 위한 수.
	vector<int> answer(n + 1, -1); // 감염에 걸리는 시간. -1로 초기화
						
	//최초 유포자는 0분. 최초 유포자 큐에 넣기.
	for (int i : firstInfected) {
		q.push(i);
		answer[i] = 0;
	}
	
	for (int i = 1; i <= n; i++) {
		turn[i] = surround[i].size() / 2; //0이 포함되어있으므로 +1 안해도 됨.
	}

	while (!q.empty()) {
		int v = q.front();
		q.pop();
		//유포자 v 주변인들 turn[] 감소
		for (int i : surround[v]) {
			turn[i]--;
			if (answer[i]==-1 && turn[i] <= 0) { //새롭게 감염되는 사람이고, 주변인들의 절반 이상이 감염자(유포자)라면
				q.push(i);
				answer[i] = answer[v] + 1;
			}
		}
	}

	return answer;
}

int main() {
	int n; // n명
	cin >> n;
	vector<vector<int>> surround(n + 1); //크기가 n+1인 벡터. 주변인 저장.
	for (int i = 1; i <= n; i++) {
		while (1) {
			int p;
			cin >> p;
			surround[i].push_back(p);
			if (p == 0)
				break;
		}
	}

	int m; //최초 유포자 수
	cin >> m;
	vector<int> firstInfected; 
	for (int i = 1; i <= m; i++) {
		int k;
		cin >> k;
		firstInfected.push_back(k);
	}

	vector<int> ans = solution(n, surround, firstInfected);
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
}