[백준 19538] 루머 (C++)

문제 링크: https://www.acmicpc.net/problem/19538

19538번: 루머

1. 주의할 점

- 루머를 퍼트리는 일은 동시에 일어난다

 

2. 구현

- BFS의 방법으로 문제를 해결한다

- Info 객체를 사용하여 현재 사람의 번호, 루머를 들은 시간, 당시에 주변에 루머 믿었던 사람 수

- rumorTime[] 배열을 이용하여 루머를 믿는 시간을 저장한다. 초기에는 init() 함수를 통해 -1로 전부 초기화한다

- nearPeople[] 배열을 통해 현재 주변에 루머 믿는 사람 수를 나타낸다

- Queue를 이용하여 BFS를 설계하며, 2개의 if문 조건을 통해 현재 사람이 아직 루머를 믿지 않지만 믿을 조건이 갖추어졌는지 확인한다

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct info {
	int idx, val, peopleNum;
};
vector<int> v[200001];
int rumorTime[200001];		//루머를 믿는 시간
int nearPeople[200001];		//주변에 루머 믿는 사람 수
int num, val, startMember;

void init() {
	for (int i = 1; i <= num; i++)
		rumorTime[i] = -1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	init();

	for (int t = 1; t <= num; t++) {
		while (1) {
			cin >> val;
			if (val == 0) break;
			v[t].push_back(val);
		}
	}
	cin >> startMember;
	queue<info> q;
	for (int i = 0; i < startMember; i++) {
		cin >> val;
		q.push({ val,0,0 });
	}
	while (!q.empty()) {
		int cidx = q.front().idx;
		int cv = q.front().val;
		int cnum = q.front().peopleNum;		//당시에 주변에 루머 믿었던 사람 수
		q.pop();
		if (rumorTime[cidx] > -1) continue;		//이미 진행된 경우		
		if (cv>0 && v[cidx].size() > 2 * cnum) continue;		//주변사람 중 반 이상 루머를 믿지 않는 경우
		rumorTime[cidx] = cv;
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			nearPeople[next]++;
			if (rumorTime[next] > -1) continue;
			q.push({ next,cv + 1,nearPeople[next] });
		}
	}

	for (int i = 1; i <= num; i++)
		cout << rumorTime[i] << " ";
	return 0;
}