[BOJ/Gold 4] 백준 19538 루머(C++)

문제 링크

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

19538번: 루머

문제

당신은 루머를 믿는가?

한 유명 심리학 실험에서는 사람들에게 두 개의 줄을 보여주고, 어떤 줄이 더 긴지 말하라 했다. 사실 한 사람을 제외하고 나머지는 실험자에 의해 사전에 조작된 사람들이었다. 조작된 사람들은 사실상 더 짧은 줄을 더 길다고 말했다. 주변 모두가 같은 답변을 하자, 진짜 피실험자 또한 짧은 줄이 더 길다고 말했다. 이 실험은 사람들이 주변인의 영향을 강하게 받는다는 것을 보여주었는데, 루머도 이와 같다.

루머는 최초 유포자로부터 시작한다. 최초 유포자는 여러 명일 수 있고, 최초 유포자를 제외하고 스스로 루머를 만들어 믿는 사람은 없다.

매분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트리며, 군중 속 사람은 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다.

루머를 믿는 순간부터 다른 말은 듣지 않기 때문에, 한번 믿은 루머는 계속 믿는다.

이때, 사람들이 루머를 처음 믿기 시작하는 시간을 알아내 보자.

입력

첫째 줄에 사람의 수 N이 주어진다. (1≤N≤200 000) 이는 1번 사람부터 N번 사람까지 있음을 의미한다.

둘째 줄부터 N개의 줄이 주어진다. 이 중 i(1≤i≤N)번째 줄에는 i번 사람의 주변인들의 번호와 입력의 마지막을 나타내는 0이 공백으로 구분되어 주어진다. 번호는 1 이상 N 이하의 자연수이고, 같은 줄에 중복된 번호는 없다. 자기 자신이 주변인이거나 일방적으로 주변인인 경우는 없으며, 전체 양방향 주변인 관계는 1 000 000개를 넘지 않는다.

다음 줄에는 루머를 퍼뜨리는 최초 유포자의 수 M이 주어진다. (1≤M≤N)

마지막 줄에는 최초 유포자의 번호가 공백으로 구분되어 주어진다. 최초 유포자의 번호는 중복되지 않는다.

출력

 N개의 정수 t1,t2,⋯,tN을 공백 단위로 출력한다. ti는 i번 사람이 루머를 처음 믿기 시작한 시간(분)이며, 충분히 많은 시간이 지나도 루머를 믿지 않을 경우 −1이다. 최초 유포자는 루머를 0분부터 믿기 시작했다고 생각한다.

예제 입력 1

7
2 3 0
1 3 0
1 2 4 0
3 5 0
4 0
0
0
2
1 6

예제 출력 1

0 1 2 3 4 0 -1

예제 입력 2

7
2 4 0
1 3 0
2 5 0
1 5 6 0
3 4 6 7 0
4 5 7 0
5 6 0
1
6

예제 출력 2

4 4 3 3 2 0 1

예제 1

0분 : 최초 유포자(1, 6번 사람)가 루머를 생성한다.
1분 : 1번 사람은 2, 3번 사람에게 루머를 퍼뜨린다. 2번 사람은 주변인 2명 중 1명이 루머를 믿고 있어 루머를 믿게 된다. 3번 사람은 주변인 3명 중 1명만 루머를 믿기 때문에, 루머를 믿지 않는다. 6번 사람은 루머를 퍼뜨릴 주변인이 없다.
2분 : 1, 2번 사람은 3번 사람에게 루머를 퍼뜨린다. 인접한 3명 중 절반 이상인 2명이 루머를 믿고 있어, 3번 사람도 2분부터 믿기 시작한다.
3분 : 3번 사람은 4번 사람에게 루머를 퍼뜨린다. 4번 사람이 믿기 시작한다.
4분 : 5번 사람도 루머를 믿게 된다. 7번 사람은 이후 충분한 시간이 지나도 루머를 믿지 않는다.

알고리즘 분류

• 그래프 탐색

풀이

어려워서 이 형님이 쓰신 글을 참고하였다.

c/c++ 백준_19538 루머

큐를 두 개를 사용해서 루머를 믿은 사람을 1번 큐에 넣고 1번 큐에 있는 사람들이 주변인들에게 루머를 퍼뜨린다.

루머를 들은 사람들은 주변인들 중 절반 이상이 루머를 믿는 상태라면 자기도 루머를 믿게 된다. 이 때 루머를 믿게 된 사람들을 2번 큐에 넣는다.

루머를 다 퍼트렸다면 2번 큐에 있는 사람들을 1번 큐에 넣고 위의 과정을 반복한다.

루머를 다 퍼뜨렸는데 2번 큐가 비었다면 루머는 더 이상 확산되지 않는다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 200005
#define LL long long
#define INF 2e9

using namespace std;
int N, M;
vector<int> Vec[MAX];
queue<int> Q, TQ;
int T[MAX];
int Time = 0;

int Rumor_People(int X) {
	int res = 0;
	for (int i = 0; i < Vec[X].size(); i++) {
		int P = Vec[X][i];
		if (T[P] >= 0) {
			res++;
		}
	}
	return res;
}

int main() {
	FIRST
	cin >> N;
	for (int i = 1; i <= N; i++) {
		while (1) {
			int P;
			cin >> P;
			if (P == 0) {
				break;
			}
			Vec[i].push_back(P);
		};
		T[i] = -1;
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int P;
		cin >> P;
		T[P] = 0;
		Q.push(P);
	}
	while (!Q.empty()) {
		int CurP = Q.front();
		Q.pop();

		// 큐에 있는 사람들이 주변인들에게 루머 유포
		for (int i = 0; i < Vec[CurP].size(); i++) {
			int nextP = Vec[CurP][i];
			if (T[nextP] != -1) {
				continue;
			}
			int Rumors = Rumor_People(nextP);
			if (((Vec[nextP].size() + 1) / 2) <= Rumors) { // 주변인들 중 절반 이상이 루머를 믿는다면 본인들도 루머를 믿게 된다.
				TQ.push(nextP);
			}
		}
		if (Q.empty()) {
			Time++;
			while (!TQ.empty()) {
				int nextP = TQ.front();
				TQ.pop();
				T[nextP] = Time;
				Q.push(nextP);
			};
		}
	};
	for (int i = 1; i <= N; i++) {
		cout << T[i] << " ";
	}
	cout << "\n";

	return 0;
}